[es] - Algoritam za formiranje Lanfordovih nizova

iggy91
Igor Peric
Sopstveni dom
Bijeljina

Član broj: 73330
Poruke: 49
*.rstel.net.

Sajt: www.zmaj.org

Profil

Algoritam za formiranje Lanfordovih nizova

^{27.05.2007. u 09:14 - pre 205 meseci}

Zadatak glasi ovako:

Lanfordov niz je niz od 27 elemenata u kome se nalaze tacno po tri od svake cifre iz intervala [1,9]. Cifre su rasporedjene tako da se izmedju scake dve uzastopne cifre I (1<=I<=9) nalazi tacno I drugih cifara.
Napisati program koji generise sve moguce Lanfordove nizove.

E sad, meni je jedino rekurzivno resenje palo na pamet, i to complete search (brute-force, nazovite kako hocete) metoda. Znaci, na svako prazno mesto J u nizu postavicu broj K (k=1...9), pri cemu cu na J+K-to mjesto postaviti takodje broj K i rekurzivno pozvati dalje postavljanje. A napisacu funkciju koja ce mi provjeravati da li je niz pravilno popunjen, cime cu brojati resenja (i ispisivati ih).

Slozenost algoritma je vrlo velika, pa ce (pretpostavljam) i vreme izvrsavanja biti neprihvatljivo.

Pada li nekome na pamet neki efikasniji algoritam?

Novac za kola se mora doneti do kraja decembra, znači do 5. decembra.
Posle pada Jakubinaca na vlast dolazi Petar Pan! :)

Odgovor na temu

cynique
Ivan Štambuk
Zagreb@Croatia

Član broj: 93690
Poruke: 155
*.cmu.carnet.hr.

ICQ: 106979934
Sajt: istambuk.blogspot.com

Profil

Re: Algoritam za formiranje Lanfordovih nizova

^{27.05.2007. u 10:15 - pre 205 meseci}

Koliko vidim postoji najviše 7! = 5040 načina popunjenja niza, što i nije neka gadna brojka za metodu "grube sile".

Započni od postavljanja slijeva na desno znamenki 9 (od najgoreg slučaja dakle - 7 mogućnosti) i za svakog od njih rekurzivno pozoveš istu fju za popunjenje, koja će u najdubljem ugniježđenju ispisivati niz jednom kad je ispravno popunjen, dok ukoliko popunjenje nije moguće napraviti samo radi "return".

Put the funk in funktion.

Odgovor na temu

cynique
Ivan Štambuk
Zagreb@Croatia

Član broj: 93690
Poruke: 155
*.cmu.carnet.hr.

ICQ: 106979934
Sajt: istambuk.blogspot.com

Profil

Re: Algoritam za formiranje Lanfordovih nizova

^{27.05.2007. u 12:51 - pre 205 meseci}

Ja gornjim algoritmom dobijem da nema rješenja :D

Za n=2 kad uradim ispis dobijem sljedeće validne permutacije (_ predstavlja još prazna mjesta u nizu u koja treba staviti 3 jedinice):

92_728_263975386435794685_4
56894_5_6478594623728329_37
6479__468574396538723529_28
86479__468574396538723529_2
4_586497534683579362_827_29

Pošto nijedne 3 _ nisu u razmaku od po 1 znamenku, slijedi da neće biti popunjenja za n=1? :-(

Vidi li tko gdje griješim?

Je li moguće da je relacija "uzastopnosti" u zadatku definirana modulo duljina niza, tako da su posljednja i druga znamenka "razmaknute" za 1 mjesto?

Put the funk in funktion.

Odgovor na temu

iggy91
Igor Peric
Sopstveni dom
Bijeljina

Član broj: 73330
Poruke: 49
*.rstel.net.

Sajt: www.zmaj.org

Profil

Re: Algoritam za formiranje Lanfordovih nizova

^{28.05.2007. u 17:26 - pre 205 meseci}

Evo rjesenja u C-u:

#include <stdio.h>
#include <stdlib.h>
int a[27],x[10],u[10],i;

int find() {
int i;
for (i=0;i<27;i++)
if (!a) return i;
return -1; }

int full() {
int i;
for (i=0;i<27;i++)
if (!a) return 0;
return 1; }

void rek(int tr,int u[]) {
int i,j,target;
target=find();
if (target+2*tr+2<27 && !a[target+tr+1] && !a[target+2*tr+2]) {
a[target]=tr;
a[target+tr+1]=tr;
a[target+2*tr+2]=tr;
x[tr]=1;
}
if (full()) {
for (i=0;i<27;i++) printf("%d ",a);
printf("\n");
}
for (i=1;i<10;i++)
if (!x && !u) {
u=1;
rek(i,u);
u=0;
}
if (x[tr]) {
a[target]=0;
a[target+tr+1]=0;
a[target+2*tr+2]=0;
x[tr]=0;
} }

int main() {
for (i=1;i<10;i++) rek(i,u);
printf("\n");
system("pause");
}

A evo i opisa algoritma:

Lanfordov niz

Opis promjenjivih:

- Niz A je deklarisan kao globalni niz i on predstavlja elemente Lanfordovih nizova.
- Niz X je binarni niz, takođe deklarisan kao globalni i njegov elemenat X[K] je u stvari binarni marker koji obilježava da li je do određenog trenutka rada programa u Lanfordov niz smještena cifra K.
- Niz U je sličan nizu X, s tim što nije deklarisan globalno, nego se predaje rekurzivnoj funkciji kao parametar, pri čemu svaka instanca pozvane rekurzivne funkcije kreira svoj primjerak niza i sve operacije izvršene unutar te funkcije nad nizom U nemaju uticaja na isti niz u prethodnim funkcijama iz koje je tekuća pozvana. Njegova svrha biće objašnjena u daljem tekstu.

Opis algoritma:

Primjenjeni algoritam je rekurzivan, i najčešće se naziva brute-force (ili complete search, što znači kompletna pretraga). Pronalaženje rešenja se vrši postepenim popunjavanjem (na početku praznog) niza A ciframa iz intervala [1,9]. Popunjavanje se odvija na sledeći način:

• Na prvo mjesto u nizu može doći bilo koja cifra iz dozvoljenog intervala, pa se glavni program sastoji iz 9 poziva rekurzivne funkcije za svako 1 <= I <= 9, šro postavlja svaku cifru na početno mjesto i nastavlja dalje popunjavanje prvog slobodnog polja.

• Pojam „popunjavanje prvog slobodnog polja“ označava postavljanje vrijednosti tri polja na neku od dosad neiskorištenih vrijednosti.

• „Tri polja“ spomenuta u prethodnoj tački su u stvari polja čije su vrijednosti K, a nalaze se na međusobnoj udaljenosti od K mjesta.
o Primjer 1: ...10101000...
o Primjer 2: ...002002002000...

• Kada se izvrši popunjavanje prvog slobodnog polja u nizu (polje sa indeksom I), binarni marker X[I] se postavlja na 1, čime se onemogućuje korišćenje tog broja u daljem popunjavanju Lanfordovog niza.

• Element U[I] se prije svakog poziva rekurzivne funkcije postavlja na 1 i niz se kao takav predaje daljoj rekurziji. Po povratku iz pozvane funkcije U[I] se resetuje na 0, čime se omogućava korišćenje tog elementa u drugim pozivima. Ovo je potrebno zbog mogućnosti da se u for petlji za dva uzastopna slobodna mjesta u nizu funkcija počne beskonačno rekurzivno pozivati. Ovim nizom se taj nedostatak zaobilazi.

• Pošto je niz X globalan, potrebno prije svakog izlaza iz funkcije „očistiti“ polja koja su na ulazu postavljena, da bi se mogla isprobati neka druga kombinacija, jer se vrijednost nekog polja može promjeniti samo ako je ono jednako nuli.

• Funkcija full() provjerava da li postoji makar jedan „prazan“ element u Lanfordovom nizu. Ako ne postoji znači da je rešenje nađeno, jer se popunjavanje organizovano tako da ako je načinjen pogrešan korak tokom popunjavanja niza, dalji pozivi funkcije sigurno neće dovesti do tačnog rješenja.

• Funkcija find() vraća indeks prvog slobodnog elementa u nizu, a ako takav ne postoji vraća -1.

Program ispisuje rješenje u fiksnom vremenu koje iznosi 0.38 sekundi, što je izuzetno prihvatljivo, s obzirom na korišćenu metoda pronalaženja rješenja i nepostojanje ulaznih podataka (a time i mogućnost izmjene složenosti algoritma).

Novac za kola se mora doneti do kraja decembra, znači do 5. decembra.
Posle pada Jakubinaca na vlast dolazi Petar Pan! :)

Odgovor na temu