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

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.
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
0

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

0

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

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.

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.

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.

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?

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.

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

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?

0

A co powiecie na coś takiego:

tab = [9, 9, 5, 4, 4, 7, 9]
tymczmin = tab[0]
najwmax = 0
najmmin = 0
licznikmax = 0
licznikmin = 0
tymczlicznikmax = 0
tymczlicznikmin = 0
roznica = 0
for licznik in range(1, len(tab)):
	temp = tab[licznik] - tymczmin
	if temp > roznica:
		najwmax = tab[licznik]
		najmmin = tymczmin
		licznikmax = licznik
		licznikmin = tymczlicznikmin
		roznica = temp
	if tab[licznik] < tymczmin:
		tymczmin = tab[licznik]
		tymczlicznikmin = licznik
print(licznikmax, licznikmin)

porównuje akutalnie przerabianą liczbę, z najmniejszą znalezioną do tej pory, wiec chyba spełni warunki zadania w jednym "przejśćiu" przez tablicę. Trochę przerabiałem ten kod, wiec mogą się trafić zbędne zmienne.

1

@anonymous23456, nie jestem pewien tego rozwiązania. Da się to na pewno zrobić podobnie. Aczkolwiek (ponieważ chyba mój komentarz nie został do końca zrozumiany) zajmę się wyjaśnieniem tamtego sposobu.
A - tablica dana
B - tablica indeksów {0...n-1}
Sortujemy B podanym wcześniej komparatorem. B[i] < B[j] wtedy, gdy A[B[i]] < A[B[j]]. Czyli indeksy są posortowane w ten sposób, że im wcześniej się pojawia, tym mniejszy element mu odpowiada w tablicy A.
Ale do tego momentu nie było chyba problemów. Zanim przejdziemy dalej, załóżmy, że tablica A jest różnowartościowa. Nie jest to wielka strata, bo możemy po posortowaniu wyrzucić dalsze indeksy takiego samego elementu w czasie liniowym i algorytm będzie dalej poprawnie działał.

Teraz zauważamy, że jeśli będziemy po kolei przechodzili po tablicy B, elementy z przerobionych indeksów są mniejsze od aktualnego. Ponadto w zmiennej pomocniczej możemy łatwo trzymać najmniejszy, przerobiony indeks. Wiec w czasie stałym odpowiemy na pytanie o parę, której końcem jest i-ty indeks. Zatem przerobić wszystkie możemy w czasie liniowym.

Poglądowy kod :

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <tuple>

using namespace std;

void my_unique(const vector<unsigned>& table, vector<size_t>& index_table) {
  vector<size_t> temp = {index_table.front()}; //Mozna bez tego, ale chyba tak latwiej zrozumiec
  for(size_t i = 1; i < index_table.size(); ++i) {
    if(table[index_table[i]] != table[index_table[i-1]])
     temp.push_back(index_table[i]);
   }
  index_table = move(temp);
 }

int main() {
  vector<unsigned> table = {9, 1, 9, 2, 9, 1, 9, 9, 3};
  vector<size_t> index_table(table.size());
  iota(begin(index_table), end(index_table), 0);
  sort(begin(index_table), end(index_table), [&](size_t i, size_t j)
                                              {if(table[i] == table[j]) return i < j;
                                               return table[i] < table[j];});
  //my_unique(table, index_table); //Ok, to nie zadziala, uwaga ponizej
  unsigned least_index = table.size(), largest_gap = 0;
  tuple<size_t, size_t> answer(table.size(), table.size());
  for(const auto& x : index_table) {
    least_index = (least_index < x) ? least_index : x;
    //Tu aktualizuj 2. zmienna. I ponizej pracuj na niej.
    if(least_index < x && largest_gap < x - least_index) {
      largest_gap = x - least_index;
      answer = make_tuple(least_index, x);
     }
   }
  if(answer == make_tuple(table.size(), table.size()))
   cout << "Brak.\n";
  else
   cout << get<0>(answer) << ' ' << get<1>(answer) << '\n';
 }
 

Edit: Powyzszy kod nie dziala, jesli jest wiele identycznych elementow.
Nie mozna skasowac wszelkich powtorek, bo istotne sa nie tylko poczatki, ale tez konce. Jesli elementy moga wystepowac dwa razy to trzeba trzymac dwie zmienne. least_index oraz least_different_index. W tej drugiej trzymac najmniejszy indeks elementu, różnego od aktualnie rozpatrywanego. Aktualizowac tak, jak pokazuje komentarz. Prosta poprawka.

0

Tym razem chyba zgodnie z warunkami zadania

def main(tab):
	najw = len(tab) - 1
	roznica = 0
	if tab[najw] > tab[0]:
		roznica = tab[najw] - tab[0]
		return (0, najw)
	naja = 0
	najb = 0
	while najw > roznica:
		for i in range(0, najw - 1):
			if tab[najw] > tab[i]:
				tymcz = najw - i
				if tymcz > roznica:
					roznica = tymcz
					naja = i
					najb = najw
			if (najw - i ) < roznica:
				break
		najw -= 1
	return (naja, najb)
a, b = main([9, 9, 5, 4, 4, 7, 9])
print(a , b)

Generalnie idę od końca jedną zmienną, a drugą od początku, jak różnica między nimi albo końcowa jest mniejsza od aktualnego "rekordzisty" to przerywam bo nie ma bo co dalej iterować (lepszego wyniku i tak nie uzyskamy, a algorytm znacznie przyśpieszy)

0

@sig : jak przerobić ten algorytm, żeby przy dwóch poprawnych wynikach wypisywał ten wcześniejszy?
przykład: dla (3, 3, 2, 3, 1, 2, 0, 0) wypisze (4, 5) a chciałbym, żeby wypisało (2, 3)

0

Problem rozwiązany, niestety Twoje rozwiązanie jest zbyt wolne, chociaż bardzo ciekawie wygląda.

0

@Tacet : natomiast Twój algorytm coś pokręcił ; D
http://ideone.com/vneGZZ

0

Jeśli to kogoś interesuje, to istnieje rozwiązanie w O(n), właśnie na nie wpadłem.

0

Algorytm:
http://pastebin.com/3reApeGf
Wybaczcie, jeśli nieco chaotycznie przedstawione.

Source code w C++:
http://pastebin.com/fJvMtfiH

Złożoność czasowa to θ(n), gdzie n jest maksymalną liczbą na wejsciu.

0

Ja miałem taką pewność, każda z liczb ma być z przedziału <0, 1e5>. Jeśli ich rozbieżność byłaby większa, to rzeczywiście inne rozwiązanie byłoby lepsze - nie oparte na tablicowaniu wystąpień liczb.

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