Szukanie indeksów tablicy o zadanych własnościach

Odpowiedz Nowy wątek
2015-01-14 00:07
anonymous23456
0

Problem jest następujący:
Mając tablice T liczb naturalnych znaleźć dwa indeksy a, b, takie, że:
1) a < b
2) T[a] < T[b]
jednocześnie uwzględniając, że wartość b-a ma być maksymalna.

Jak na moje oko: albo masz chwilowe zaćmienie albo rezygnuj z kierunku natychmiast. - _13th_Dragon 2015-01-14 00:44

Pozostało 580 znaków

2015-01-14 00:41
0

Dla: T(1..N);

  1. a=1
  2. b=N
  3. Wyświetl odpowiedź na pytanie 1. a, b
  4. dopóki T(a)>=T(b) rób
  5. # a=a+1
  6. # b=b-1
  7. koniec pętli
  8. Wyświetl odpowiedź na pytanie 2. a, b

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2015-01-14 13:44
anonymous23456
0

Chyba się nie zrozumieliśmy.
9 9 5 4 4 7 9

Pozostało 580 znaków

2015-01-14 13:46
anonymous23456
0

Btw, nie sądzę, żebyś zrozumiał pytanie. Odpowiedź do powyższego to 2, 6, dla T[0...6].

Pozostało 580 znaków

2015-01-14 13:51
anonymous23456
0

Chyba rozumiem już problem: otóż wszystkie warunki zadania muszą być spełnione równocześnie. Więc albo masz jakieś zaćmienie, albo nieco bardziej szanuj innych użytkowników.

Pozostało 580 znaków

2015-01-14 13:57
0

Spróbuj rekurencyjnie. Znając prawidłową odpowiedź dla tablicy [0,k] sprawdź czy lepsza jest dla [0,k+1] z tym dodatkowym elementem.


"There are people who actually like programming. I don't understand why they like programming."
Rasmus Lerdorf

Pozostało 580 znaków

2015-01-14 14:01
anonymous23456
0

Dla [0,k] musiałbym wtedy trzymać drugą, posortowaną tablice liczb [T[0],T[k]], żeby szybko stwierdzić, co dzieje się dla [0,k+1]. Rozwiązanie raczej nie wydaje się optymalne, a sądzę, że istnieje algorytm z O(n). Chyba, że o inny rekurencyjny sposób Ci chodzi.

A nie zadowoli Ciebie O(n lg n)? Bo wtedy wystarczy posortować tablice B indeksów tablicy danej A (komparator: B[i] < B[j], gdy A[B[i]] < A[B[j]]) i przelecieć się po niej w O(n). Ogólnie nie widzę na pierwszy rzut oka możliwości stworzenia rozwiązania działającego w czasie O(n), co oczywiście nie znaczy, że go nie ma. Zmęczony jestem, kartki nawet nie wziąłem... - Tacet 2015-01-14 15:43

Pozostało 580 znaków

2015-01-15 03:48
anonymous23456
0

@Tacet :
A = {9, 9, 5, 4, 4, 7, 9}
B = {0, 1, 6, 5, 2, 3, 4} (zmieniłem relacje na >=, wydaje się odpowiedniejsza)
Teraz musimy robić tak:
Dla każdego indeksu k tablicy B wyszukujemy w B[k+1, koniec_tablicy] element maksymalny. Rozwiązujemy to wykorzystując następujące własności:
-B jest tablicą liczb {0, 1, 2, ..., n}
-max w tablicy B[0..n] to n
-max w tablicy B[1..n] to: B[0] == n ? n-1 : n. Cała reszta tablicy analogicznie.
Mamy zatem dla każdego elementu w A maksymalny indeks elementu większego od niego, lęzącego na prawo. Bingo, liniowe przejście i załatwione. Całość o złożoności logn + 2n. Czy to wygląda zbyt różowo czy powinno być okej?

Pozostało 580 znaków

2015-01-15 08:29
0

Wygląda zbyt różowo. Weź zdefiniuj porządnie czym jest tablica B. Bo teraz nie wiadomo o co Ci z nią chodzi, a według mnie to szukanie max w tablicy B jest wątpliwe.


"There are people who actually like programming. I don't understand why they like programming."
Rasmus Lerdorf

Pozostało 580 znaków

2015-01-15 10:17
0
#include <iostream>
using namespace std;

int main()
  {
   int tb[]={ 9, 9, 5, 4, 4, 7, 9 };
   int size=sizeof(tb)/sizeof(*tb);
   for(int i=size-1;i>0;--i)
     {
      for(int k=0;i+k<size;++k)
        {
         if(tb[k]<tb[i+k])
           {
            cout<<k<<' '<<(i+k)<<endl;
            i=0;
            break;
           }
        }
     }
   return 0;
  }

http://ideone.com/2U3ffx


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
Ale to ma złożoność O(n^2). - bogdans 2015-01-15 12:54
Jak na razie nie widzę lepszej. - _13th_Dragon 2015-01-15 14:16
Da się w O(n log n) - hauleth 2015-01-15 23:03
Tak, jest dalej pokazane. - _13th_Dragon 2015-01-15 23:04

Pozostało 580 znaków

2015-01-15 15:10
anonymous23456
0

Prawdopodobnie rozwiązanie w O(n) sprowadza się do:
mając tablice B[0..n] kolejnych liczb naturalnych, wyznaczyć maxB[0..n], maxB[1..n], ...
czyli wartości maksymalne wszystkich przedziałów końcowych tablicy. Jakieś pomysły?

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0