Znajdowanie zależności w tablicy

Jak rozwiązać następujący problem: Dana jest tablica 100 tyś elementów typu int (int ar[10000]) kolejne komórki tablicy zawierają liczby, które są generowane na podstawie indeksu komórki, pewnym nieznanym algorytmem. Należy znaleźć zależność pomiędzy wartością komórki a jej indeksem i wyrazić rozwiązanie w postaci funkcji przyjmującej jako parametr wartość pewnej komórki, a zwracającej numer indeksu (lub numery indeksów - bo wartości komórek mogą się powtarzać). Myślałem o sieci neuronowej, ale może jest jakieś prostsze rozwiązanie.

Wiem jeszcze jedno, wartości w komórkach są generowane pseudolosowo, ale dobra informacja jest taka, że indeks jest seedem. Przeszukiwanie liniowe odpada, ponieważ w finalnej wersji programu nie wolno korzystać już z tablicy. Tablica ma zatem tylko służyć do napisania odpowiedniej funkcji - i tylko ona ma prawo być w finalnej wersji programu.

2 lata, 3 miesiące temu | edytowane przez: komorra 250317

Odpowiedz na pytanie

3

Odpowiedzi: 5

  • 2 lata, 3 miesiące temu
    autor: lqc

    8

    Jeżeli nie masz jakiegoś ograniczenia na to jaka jest ta zależność (np. linowa, wielomiany, funkcje elementarne), to problem jest raczej nierozstrzygalny, a już na pewno nie jest jednoznaczny, bo w końcu to tylko 100000 elementów.

    Niech pod indeksem k, znajduje się wartość a_k. Weźmy:

    L_k(x) = (x-1)(x-2)...(x-k+1)(x-k-1)...(x-100000)/(k-1)(k-2)...(k-100000)
L_k(i) = 0, dla każdego i != k
L_k(k) = 1

    Wystarczy wziąć ∑k100000akLk(x) i już masz wielomian opisujący tę tablicę.

    Jest to algorytm generowania tablicy jak każdy inny. Ma po prostu 100000 parametrów, tylko które mogłem sobie wziąć z sufitu.

    Seed i losowe liczby

    Nadal tego jakoś nie widzę. Szansę na sukces masz tylko jeśli okres tego PRNG jest mniejszy niż 100000. Wtedy możesz znaleźć cykl w tej tablicy. Ale w sumie też nie masz pewności, bo może raz na 300000 elementów seed jest przesuwany cyklicznie o 1. Pewności nigdy nie możesz mieć.

  • 2 lata, 3 miesiące temu
    autor: michu

    3

    Jeżeli chodzi jedynie o wyszukanie indeksów, to nie potrzebujesz do tego algorytmu, tylko liniowo przejrzeć tablicę i wybrać indeksy dla których wartość się zgadza. 100.000 to jest żadna ilość, nie problem z przeszukaniem. Ale podejrzewam, że nie o to chodzi bo byłoby za prosto...

    Jeżeli rzeczywiście chodzi o reverse engineering algorytmu, to jest to bardziej zadanie na inteligencję i umiejętności detektywistyczne... Spróbuj sobie to najpierw wyrysować i zobaczyć czy wykres przypomina jakąś typową funkcję - np. wielomian czy coś takiego. Dopiero mając jakieś charakterystyki tego zbioru danych można myśleć co dalej...

  • 2 lata, 3 miesiące temu
    autor: borzole

    1

    Tak spojrzałem na to jeszcze raz, czy Tobie może chodzi o wykonanie po prostu aproksymacji lub interpolacji danych do funkcji.

    Wpisz w google:
    aproksymacja site:edu.pl
    interpolacja site:edu.pl
    to dostaniesz pełno gotowych algorytmów

  • 2 lata, 3 miesiące temu
    autor: nilphilus

    0

    Najprościej to można wyciągnąć wzór: choćby tak jak się to robiło w ciągach, ale nie powiem dokładnie bo to było dawno temu, ja dawno temu tego nie potrzebowałem. (ale pamiętam że jakoś tak rozwiązywałem pytanie na SPOJu - na dobrą sprawę masz trochę informacji zdaje się :-) )

  • 2 lata, 3 miesiące temu
    autor: borzole

    0

    Kiedyś na zajęciach z algorytmów genetycznych widziałem coś takiego napisanego w LISP (podobno język w sam raz do takich problemów). Program dostawał (pseudo) losowe dane i starał się dopasować wzór jaki opisuje ten zbiór danych. Im dłużej program działał tym lepsze dopasowanie znajdował. Rozwiąż ten problem w LISP, a potem ewentualnie spróbuj przenieść na inny potrzebny Ci język.

    [edycja]

    nie mam materiałów w wersji elektronicznej, ale jest google:
    "algorytmy genetyczne" site:edu.pl

Zaloguj się, aby dodać swoją odpowiedź