Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Kako biste resili sledeci zadatak?

[es] :: Art of Programming :: Kako biste resili sledeci zadatak?

[ Pregleda: 8154 | Odgovora: 17 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

vdivac
Vladan Divac

Član broj: 60420
Poruke: 7
*.etf.bg.ac.yu.



Profil

icon Kako biste resili sledeci zadatak?17.06.2005. u 19:54 - pre 228 meseci
Potrebno je resiti nesto sto neodoljivo podseca na sadasnji "Moj broj" iz slagalice.

Kao ulazne parametre imate 6 polaznih brojeva (4 od njih su izmedju 1 i 9, jedan je iz skupa [10,15,25] a jedan iz skupa [50,75,100]) i trazeni broj (izmedju 1 i 999).
Potrebno je stampati izraz cija je vrednost tacan broj ukoliko takav izraz postoji odnosno izraz sto priblizniji tacnom resenju ukoliko je nemoguce dobiti tacno resenje.
U izrazu je dozvoljeno upotrebiti polazne brojeve najvise jednom, dozvoljene su operacije +, -, X, / i zagrade. Pri tome je potrebno prihvatati i resenja u kojima neki od operanada nije ceo broj, ali rezultat jeste, npr
Ulaz:
8, 7, 6, 6, 15, 75 //polazni brojevi, prvi red ulaznog fajla
985 //broj koji treba dobiti, drugi red ulaznog fajla
Izlaz:
985 //najblizi broj koji je kompjuter nasao u prvom redu
(75-8*7/6)*15 //zapis(i) tog broja u sledecem redu (sledecim redovima)
U slucaju da vise izraza daje tacan rezultat treba stampati izraz(e) sa najmanje upotrebljenih polaznih brojeva. Izraz ne sme da sadrzi nepotrebne zagrade. U slucaju da ne postoji tacno resenje, a postoje dva po apsolutnoj vrednosti jednako udaljena resenja od tacnog resenja, treba stampati rezultate za veci broj.
Rezultat treba da se pojavi za manje od 5 sec na Pentium 200Mhz.
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*



+1 Profil

icon Re: Kako biste resili sledeci zadatak?17.06.2005. u 22:53 - pre 228 meseci
Pa tu ne mozes nista pametno da smislis. Jenostavno moraces sve kombinacije da proveravas i da pamti najblizu... (smrc)
Math is like love. A simple idea but it can get complicated.
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*



+1 Profil

icon Re: Kako biste resili sledeci zadatak?18.06.2005. u 00:38 - pre 228 meseci
Kad smo vec na ovome:

Da li je moguce pomocu brojeva i osnovnih operacija , uz koriscenje zagrada, dobiti broj ? (bez koriscenja racunara molim....)
Math is like love. A simple idea but it can get complicated.
 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Kako biste resili sledeci zadatak?18.06.2005. u 02:52 - pre 228 meseci
6*4=24 ??
I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*



+1 Profil

icon Re: Kako biste resili sledeci zadatak?18.06.2005. u 03:22 - pre 228 meseci
Ja se izvinjavam... Nisam napomenuo da svaki broj mora da se upotrebi tacno jednom... :-)
(naravno njih mozete koristiti samo kao cifre a ne npr. kao 13, 34, 16...)
Math is like love. A simple idea but it can get complicated.
 
Odgovor na temu

Sundance

Član broj: 7510
Poruke: 2559
*.sava.sczg.hr.



Profil

icon Re: Kako biste resili sledeci zadatak?18.06.2005. u 03:44 - pre 228 meseci
Sorry za ovo maloprije...dokazao sam da se ne može, ali vjerojatno sam u krivu :)

Preglup problem da se rješava razmišljanjem, brijem da ima svega 64*6 (ili možda malo više :) mogućnosti, idealno za brutforsanje :>
 
Odgovor na temu

vdivac
Vladan Divac

Član broj: 60420
Poruke: 7
*.tmf.bg.ac.yu.



Profil

icon Re: Kako biste resili sledeci zadatak?18.06.2005. u 12:23 - pre 228 meseci
Nisi u pravu Sundance. Ima MNOGO vise mogucnosti od 64*6. Rez je o milionima. Samo izraza duzine 2 (sastavljenih od dva broja i operanda izmedju njih) koji u opstem slucaju mogu generisati razlicite vrednosti ima 6*5/2 za sabiranje i mnozenje (posto tu nije bitan redosled operanada) i 6*5 za oduzimanje i deljenje tj. ukupno 90. A izraz koji koristi npr 5 od datih brojeva se moze dobiti kao npr kolicnik nekog izraza duzine 3 i izraza duzine 2, pod uslovom da oni u svom zapisu ne koriste iste brojeve).
Slazem se da je potreban brute force, ali i taj brute force mora da bude pametno osmisljen. Ne mozes, na primer, da generises sve izraze duzine 2x+1 koji se sastoje od x+1 operanada i x operatora (x ide od 1 do 5), potom da proveris da li se radi o postfiksnoj notaciji i da izracunas vrednost izraza ako on predstavlja postfiksnu notaciju, jer se to nikad nece izvrsiti u navedenim vremenskim granicama. (Ovo je bila moja prva ideja, veoma glupa - priznajem, mada radi za do 4 ulazna broja).
Da rezimiram, ovde je pitanje kako napraviti sto efikasniji brute force.
 
Odgovor na temu

MilosSavic

Član broj: 61272
Poruke: 24
*.pat-pool.nsad.sbb.co.yu.



Profil

icon Re: Kako biste resili sledeci zadatak?18.06.2005. u 14:32 - pre 228 meseci


E a da li neko zna kako pomocu cetiri sedmice i jedne jedinice i osnovnih racunskih operacija +, -, *, / da dobije 100....
A potom da li neko zna kako pomocu cetiri cetvorke da dobije sve brojeve od 1 do 50 a onda i sve brojeve iz N ....

P.S Kad backtrack ne pomaze, probaj da sklopis kakvu manje vise uspesnu heuristiku...
P.S.2 Inace ako nisi vec provalio do sada, ti ljudi na slagalici varaju... Oni vec osmisle resenje, pa onda kao ti kazes stop a on ti ustvari izbaci ne ono sto si ti zaustavio nego ono sto je on vec namenio da bude zaustavljeno... Ista fora je i sa slagalicom.... Smisle srpsku rec od 10 slova, dodaju jos 2, pa ti onda random nalupaju tih 12 slova.... I tako dobiju algoritme koji rade u savrseno perfektnom vremenu O(1)... Inace u PSC na seminarima racunarstva mi smo davali klincima ovaj zadatak (pored zadatka cuvene barbare gde klinci treba da provale sta je to konacan automat) i svi su manje vise dosli do onog malkice pametnijeg resenja (napravi se recnik srpskih reci koji se sortira po duzini reci u opadajucem poretku, pa se onda pretrazuje taj recnik i proverava da li su slova trenutne reci u skupu izabranih slova, pretrazivanje se zaustavlja kada se naleti na prvu takvu rec, koja je onda i najduza)
P.S.2 Efikasniji bruteforce od bruteforceta kao takvog ne mozes napraviti :)...



pozdvafi Milos
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*



+1 Profil

icon Re: Kako biste resili sledeci zadatak?18.06.2005. u 15:51 - pre 228 meseci
Znaci, slazem se sa Savicem... Ovo, cak sta vise ja sam kao premotavao film, i setio se (ali ne i nasao na kompu) da sam ja kucao taj program (cak je kucao i moj burazer) i da je prolazio za 1 sec. Siguran sam da je bio cist backtrack. Ako nadjem postavicu...

P.S. O Milsav otkud ti...
Math is like love. A simple idea but it can get complicated.
 
Odgovor na temu

zvrba
The Lord of Chaos

Član broj: 31716
Poruke: 105
*.uio.no.



Profil

icon Re: Kako biste resili sledeci zadatak?18.06.2005. u 18:22 - pre 228 meseci
evo rjesenje, napisao sam ga jos davno na faxu u inat asistentu koji je tvrdio da je to puno jednostavnije u prologu :) Hardkodirano je 5 brojeva, ali to se lako promijeni na par mjesta. Moguc problem je i nepostojeci <alloca.h> header koji je platform-dependent. Npr. na FBSD-u ne postoji vec je dovoljno includeati samo <stdlib.h>.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <alloca.h>
#include <limits.h>

struct node {
  char oper;
  int num;
  struct node *left, *right;
};

int error = INT_MAX;
int goal;

void erase(struct node *in[], struct node *out[], int i1, int i2, int total)
{
  int i;

  for(i = 0; i < total; i++) {
    if(i == i1 || i == i2) {
      in++;
    } else {
      *out++ = *in++;
    }
  }
}

void print_tree(struct node *tree)
{
  if(tree == NULL) return;
  if(tree->oper != 0) {
    printf("("); print_tree(tree->left); printf(")");
    printf("%c", tree->oper);
    printf("("); print_tree(tree->right); printf(")");
  } else {
    printf("%d", tree->num);
  }
}

void solve(struct node *numbers[], int n)
{
  struct node *a, *b;
  struct node *new[5];
  int i, j;

  if(n == 1) {
    if(abs(numbers[0]->num - goal) < error) {
      error = abs(numbers[0]->num - goal);
      print_tree(numbers[0]);
      printf(" = %d\n", numbers[0]->num);
    }
  }
  
  for(i = 0; i < n; i++) for(j = 0; j < n; j++) if(i != j) {
    a = numbers[i]; b = numbers[j];
    erase(numbers, new, i, j, n);
    
    new[n-2] = alloca(sizeof(struct node));
    new[n-2]->left = a; new[n-2]->right = b;
    
    new[n-2]->num = a->num + b->num; new[n-2]->oper = '+'; solve(new, n-1);
    new[n-2]->num = a->num - b->num; new[n-2]->oper = '-'; solve(new, n-1);
    new[n-2]->num = a->num * b->num; new[n-2]->oper = '*'; solve(new, n-1);
    if(b->num != 0 && a->num % b->num == 0) {
      new[n-2]->num = a->num / b->num; new[n-2]->oper = '/';
      solve(new, n-1);
    }
  }
}

int main()
{
  int i;
  struct node *numbers[5];

  for(i = 0; i < 5; i++) {
    numbers[i] = malloc(sizeof(struct node));
    numbers[i]->left = numbers[i]->right = NULL;
    numbers[i]->oper = 0;

    printf("Enter number %d: ", i+1);
    scanf("%d", &numbers[i]->num);
  }
  printf("Enter goal: ");
  scanf("%d", &goal);

  solve(numbers, 5);
  
  return 0;
}
 
Odgovor na temu

stf

Član broj: 51276
Poruke: 65
*.185.EUnet.yu.



Profil

icon Re: Kako biste resili sledeci zadatak?18.06.2005. u 19:06 - pre 228 meseci
Citat:
cassey: Kad smo vec na ovome:

Da li je moguce pomocu brojeva i osnovnih operacija , uz koriscenje zagrada, dobiti broj ? (bez koriscenja racunara molim....)




If you don't live for something, you will die for nothing.
 
Odgovor na temu

MilosSavic

Član broj: 61272
Poruke: 24
*.pat-pool.nsad.sbb.co.yu.



Profil

icon Re: Kako biste resili sledeci zadatak?20.06.2005. u 14:53 - pre 228 meseci

Naravno da jeste lakse i jednostavnije napisati u Prologu. Zasto?
Ako pogledas, aritmeticke izraze lingvisticki mozes zapisati u sledecoj gramatici:
expr->expr + term
| expr - term
| term
term -> term * factor
| term / factor
| factor
factor -> number
|unop number
| (expr)
unop -> +|-
Sada ovo lako mozes pretociti u proloske klauze bas isto ovako :), tj. od svake gramaticke produkcije pravis jednu prolosku klauzu. Svaka klauza ima kao argument listu, sa tim sto expr kao argument ima listu svih "zaustavljenih" brojeva, kasnije kako propadas backtrackom kroz klauze smanjujes tu listu, tako da ti klauza faktor ima kao argument najcesce jednoelementnu listu i ta klauza je zadovoljena ukoliko je nesto sto je prosledjeno njoj nije prazna lista (*tj, ako je jedan od izabranih brojeva, onda super, a ako nije onda opet pokusavas da zadovoljis expr klauzu *). Prva klauza tvog proloskog programa bi onda trebala biti jednostavna klauza koja pravi permutacije liste odabranih brojeva, a zatim pokusava da zadovolji klauzu expr :) Sve u svemu 11 linija koda :)
O performansama je izlisno govoriti jer mi uglavnom danas programiramo na racunarima cija je arhitektura naredbi prilagodjena imperativnim programskim jezicima, verovatno bi na procesoru koji ima u sebi hardverski ugradjene mehanizme supstitucije i rezolucije ovaj programcic znatno brze radio nego ekvivalent zapisan u nekom od imperativnih programskih jezika (*a secam se kada sam imao 10 godina (*a to je bilo pre 10 godina (* ugnjezdeni komentari, zivela Modula-2 *) *) takvi racunari, tj. racunari pete generacije koji imaju bas to ugradjeno su pompezno najavljivani, posle je projekat propao, mada su i kod nas objavljene neke knjige na tu temu *)
Ako pogledas tvoj program, on ima red velicine 10^2 linija, mozda je moglo i manje da nisi pokusavao da nam/asistentu pokazes da znas da programiras u C-u (*kako volim te programere koji pisu svoje programe koristeci najegzoticnije mogucnosti C-a *) Cak, ne znam zasto odzavas svoju strukturu binarnog stabla, kada si se usmerio na rekurzivno nametnuto resenje problema (*ah, sve je rekurzija *), posto u toku rekurzije na steku imas interno odradjeno to tvoje stabaoce :)
Da se vratimo opet na Prolog, resenje u prologu, iako elegantno, u sebi krije manu, jer ako vi njemu kazete
?-solve([3, 4, 5, 8, 10, 75, 345])
on vam kaze yes/no i istampa resenje, medjutim sta ako resenja nema :) E onda, nista od prologa, nego se opet moramo dovijati u imperativnim programskim jezicima :)
Vec sam pomenuo da bi bilo dobro napraviti neku heuristiku :) Jer sigurno je onaj igrac koji ucestvuje u igri ne pravi sve kombinacije zaustavljenih brojeva, jos gore prateci neki backtrack algoritam :) Uigrani igraci znaju da postoji nekoliko fora na tu temu :) Evo recimo prva heuristika: neka se treba konstruisati broj a, pri tome je broj b jedan iz skupa {50, 100, 75}, c jedan iz skupa {10, 15, 20 (*ili tako nesto *)}, a d onaj jedan od cetiri jednocifrena :) Tada je ono sto bih ja prvo probao da uradim podelio a sa b i dobio c1, zatim podelio c1 sa c i iz skupa d odabrao onaj koji je najblizi c1/c i super imam jedno resenje (jer opet napominjem, cilj igre nije samo dobiti tacno resenje, jer mozda ono i ne postoji)... Ono sto se postavlja kao pitanje koje se uvek postavlja kada se problem resava heuristicki jeste uspesnost te heuristike (* Ova verovatno i nije bas nesto uspesna *), tj, trebalo bi sada napisati monte-karlo simulaciju koja ti razigrava tvoj univerzum brojeva i resava prvo heuristikom, a onda standardno bektrekom i za razigranih recimo N univerzuma, nadji n, tj. broj slucajeva kada se resenja poklapaju :) Tada se uspesnost heuristike meri kao verovatnoca n/N sa greskom koja se skalira kao koren iz jedan sa N... Siguran sam da se nadgradnjom ove heuristike (tj, ubacite malo if-ova, pokusavate da delite sa nekim zbirom iz unije skupova c i d), mogla dobiti veoma uspesna heuristika koja radi u vremenu O(1) a sto bi nam i svima bio cilj :) Jer poenta heuristickog pristupa jeste (*da se filozofski odrazim *) ne menjati entropiju univerzuma, ako si vec u tvojim monte-karlo simulacijama heuristike izracunao p (*koje su opet slozenosti onolike kolike ti zelis da budu, jer ti odredjujes sa koliko procesorskog vremena zelis da pretrazujes tvoj kompleksni univerzum u potrazi za specijalnim slucajevima koje ruse tvoju heuristiku, monte-karlo je super jer je O(n) (*jer je najobicniji random walk kroz tvoje stablo univerzuma *) a uvek znas sa kolikom greskom si ocenio p *), samo sklopis resenje, kao da je uvek bilo tamo :)

E Andrejko, eto jurim ove moje po forumima :) Vidimo se u skorije vreme u PSC, vrlo je verovatno :) Jedino ako ne odes na tu olimpijadu, pa postanes izgubljena dusa kao i ostali koji zavrse u toj sekti :)

Drugo ne vidim da je iko razmisljao o ona dva zadacica... Verujte mi veoma su korisna :) Ako sami to izmozgate, jos posebno ako ste mladi, recimo 7. ,8. ili 1. razred onda je stvarno velika slava i veliki putevi pred Vama :) Ja sam sa ta dva primera, tj. sa prvim pokusao klincima koji su sedmi razred da objasnim zasto je dobro ponekada promeniti referentni sistem, tj. ugao na koji gledas na problem :) Reci cu samo jos ovo, ako biste pokusali da napisete program koji bi Vam konstruisao resenje (*sto je naravno moguce ako ste pratili ovaj post *), onda Vam kazem takav program ne mozete napisati u strogo tipiziranim programskim jezicima (*aka, java, modula-2*)? (*nadam se da cete posle ovoga ostati zaintrigirani *), a ako uspete da izmozgate drugi zadatak, onda ste verovatno izmislili Peanovu aksiomatiku, osetili potrebu lingvistickog pristupa u matematici (*vec pomenute gramatike *) i pronasli dve od tri fundamentalne funkcije u teoriji rekurzivnih funkcija koja je osnov matematickog zasinivanja racunarstva :) (* tj, ono sto mi mozemo i znamo da izracunamo jeste po svojoj prirodi rekurzivno (* fraktal, seko, fraktal *) *)

I toliko ne bih Vise da smaram cenjeni auditorijum :)

pozdravi Milos
 
Odgovor na temu

zvrba
The Lord of Chaos

Član broj: 31716
Poruke: 105
*.uio.no.



Profil

icon Re: Kako biste resili sledeci zadatak?20.06.2005. u 15:22 - pre 228 meseci
Citat:
MilosSavic
Ako pogledas tvoj program, on ima red velicine 10^2 linija, mozda je moglo i manje da nisi pokusavao da nam/asistentu pokazes da znas da programiras u C-u (*kako volim te programere koji pisu svoje programe koristeci najegzoticnije mogucnosti C-a *) Cak, ne znam zasto odzavas svoju strukturu binarnog stabla, kada si se usmerio na rekurzivno nametnuto resenje problema (*ah, sve je rekurzija *), posto u toku rekurzije na steku imas interno odradjeno to tvoje stabaoce :)

Kako dozlaboga nepregledno i lose napisan tekst!

No anyway, koje ja to "egzoticne" mogucnosti koristim? alloca? to nije egzotika. U C99 je zamijenjeno sa standardnim VLAs.

A odrzavam stablo zato da bih mogao isprintati izraz! Setnja po runtime C stacku nije nimalo portabilna cak niti na jednom kompajleru na jednoj arhitekturi (npr. razne optimizacije). Da ne govorim da se argumenti mogu prenosti registrima a ne preko stacka.

Citat:

Da se vratimo opet na Prolog, resenje u prologu, iako elegantno, u sebi krije manu, jer ako vi njemu kazete
?-solve([3, 4, 5, 8, 10, 75, 345])
on vam kaze yes/no i istampa resenje, medjutim sta ako resenja nema :) E onda, nista od prologa, nego se opet moramo dovijati u imperativnim programskim jezicima :)

Vec sam pomenuo da bi bilo dobro napraviti neku heuristiku :)

Covjece o kakvoj ti heuristici pricas? Kaj nije moguce u Prologu napravit da vraca najblize rjesenje kao sto to radi moj program? Cak i ako nema rjesenja (i ne trazi se najblize nego tocno), dobro napisani prolog progam ce iscrpiti sve mogucnosti i na kraju odgovoriti No. Nece se zavrtiti u beskonacnoj petlji.

Citat:

Reci cu samo jos ovo, ako biste pokusali da napisete program koji bi Vam konstruisao resenje (*sto je naravno moguce ako ste pratili ovaj post *), onda Vam kazem takav program ne mozete napisati u strogo tipiziranim programskim jezicima (*aka, java, modula-2*)?

Kako se ne moze? Pa C je isto strogo tipiziran pa ovo radi. Da ne govorim da se sve na kraju izvrsava na procesoru koji itekako ima strogo tipizirane instrukcije.

Citat:

Drugo ne vidim da je iko razmisljao o ona dva zadacica... Verujte mi veoma su korisna :)

Koja dva? 4 sedmice i jedinica te 4 cetvorke?

Sa prvim ne zelim gubit vrijeme.

Sto se tice cetiri cetvorke, ako imas na raspolaganju konacan skup proizvoljnih funkcija f : NxN -> N jednostavno je nemoguce generirati sve prirodne brojeve jer postoji samo konacno mnogo mogucih kompozicija tih funkcija.
 
Odgovor na temu

MilosSavic

Član broj: 61272
Poruke: 24
*.pat-pool.nsad.sbb.co.yu.



Profil

icon Re: Kako biste resili sledeci zadatak?21.06.2005. u 15:01 - pre 228 meseci


Bicu kratak,

1) Sta me briga sto je tekst lose napisan, ah, pa to je subjektivna stvar, ko ne zeli da cita, ne mora :) U svakom slucaju, ko zeli mogao bi pronaci par korisnih detalja :0
2) Stvar se moze resiti bez upotrebe pointerske aritmetike koju svi C programeri tako silno obozavaju (to je egzotika, je*o nas Ritci koji se izivljavase na nama nudeci nam g**** od jezika, banderas jedan, ma gori smo bili mi sto ga prihvatismo :)), a koja je u ovom slucaju krajnje nepotrebna... Probaj na primer da istu stvar isprogramiras u Moduli-2.... I onda kazes pointer, sta to bese i kome to treba?
3) Da li si kada video da rekurzivni parser koji parsira rekurzivne gramatike (ovo je najgori slucaj) odrzava stablo zavisnosti izraza. Odgovor je ne jer to nije potrebno. Drugo nisam rekao da ti treba da setas po steku, to u visim pj i nije moguce, samo kazem da to tvoje stabaoce koje ti pravis vec postoji na steku, ali kao kod svakog stabla ti radis sa glavom, levim i desnim podstablom, sve sto ti treba od levog ili desnog podstabla dobijas rekurzivnim pozivom kada kao argument glave stavis pointer na levo ili desno podstablo :) Hocu reci, lose logicki organizovan program, u ovom slucaju ako problem resavas rekurzivno stablo zavisnosti izraza ti uopste nije potrebno, ako ga imas i odrzavas, onda samo dupliras stvari :) Jer to stablo IMPLICITNO vec postoji na steku, setnja po stablu a da nije okolina (levo, desno) ti nikada i nije potrebna, podatke dobijas kroz parametre i povratne vrednosti rekurzivnih poziva.
4) Naravno da je moguce, kao sto je sve sto je deterministicki moguce isilovati na svim deterministickim platformama, ali onda nije 11 linija koda :) To je bila poenta, Mislio sam na tacno resenje, ne na najbliza po apsolutnoj razlici priblizna resenja.
5) Prolog nema petlje, niti poznaje taj koncept... Beskonacne petlje nikada nisam ni pominjao, tako da ne znam o cemu pricas, niti ce predlozeno resenje ikada upasti u nesto sto ti zoves beskonacnom petljom (opet ponavljam to u prologu ne postoji), jer sam naglasio da se klauza nezadovoljava kada je argument klauze prazna lista, a to ce se kad tad desiti, tj. desice se ako nema tacnog resenja :)
6) Ah, C NIJE STROGO TIPIZIRAN jezik, jer u c-u mozes da napises
float a = 10.0;
int b = 10;
int c = a + b;
To u moduli-2 ili javi ne mozes ovo da napises jer argumenti izraza nisu istog tipa (jedan je float, drugi int, java kompajler ti kaze ne, ne prijatelju nisu istog tipa ajde ti odradi neki cast) :) Ovo samo pokazuje da nikada nisi programirao u nekom od strogo tipiziranih programskih jezika (okej, jesi bar u jednom, asembleru) :) Ili ne znas programerski da razmisljas, sto je jos gore :) (*ah sto sam okrutan *)
7) C je programski jezik viseg nivoa i to nema nikakve veze sa procesorom na kome izvrsavas C-ovski program, jer se C-ovski programi "izracunavaju" na uopstenom proceduralno-struktuiranom apstraktnom matematickom modelu racunara :) Asemblerske instrukcije su strogo tipizirane ali sa operandima koji su svi istog tipa podataka (db, dw ili dd) i opet ponavljam to nema nikakve veze sa visim programskim jezicima... Do kompajlera je, a to nas ne interesuje, kako ce te razlike u modelima da nadomesti :) A to nije nikakav problem ako znamo da se svi prosti tipovi podataka na neki nacin mogu kodirati integerima, to jest na asemblerskom nivou wordovima.
8) Super, to znaci da prvi nisi u stanju da resis :) Iako je zaista lak :) Jedan genije manje :)
9) Negativno, ako imas jedan operand (na primer u zadatku operand koji je uvek konstanta 4) i jednu unarnu funkciju (na primer -) onda mozes napraviti beskonacno mnogo (htedoh reci beskonacno prebrojivo) kompozicija te unarne funkcije, na primer ovako
f1(x) = x
f2(x) = -f1(x)
...
fn(x) = -fn-1(x)
...
To je prvi korak u mozganju... Mala pomoc, setite se operatora ++ :) To je vec 95% resenja.

pozdravi Milos
 
Odgovor na temu

zvrba
The Lord of Chaos

Član broj: 31716
Poruke: 105
*.ifi.uio.no.



Profil

icon Re: Kako biste resili sledeci zadatak?22.06.2005. u 08:14 - pre 228 meseci
Citat:
MilosSavic: Bicu kratak,
9) Negativno, ako imas jedan operand (na primer u zadatku operand koji je uvek konstanta 4) i jednu unarnu funkciju (na primer -) onda mozes napraviti beskonacno mnogo (htedoh reci beskonacno prebrojivo) kompozicija te unarne funkcije, na primer ovako
f1(x) = x
f2(x) = -f1(x)
...
fn(x) = -fn-1(x)
...
To je prvi korak u mozganju... Mala pomoc, setite se operatora ++ :) To je vec 95% resenja.

pozdravi Milos


E ali ti si postavio zadatak da imas SAMO 4 cetvorke! Znaci ne mozes napraviti prebrojivo beskonacno mnogo kompozicija jer ces prije ili poslije potrositi svoje 4 cetvorke!

Ako je dozvoljeno beskonacno mnogo puta trositi _medjurezultate_ (nesto sto u originalnoj varijanti zadatka nije dozvoljeno - svaki medjurezultat smijes/moras potrositi samo jednom), onda je rjesenje trivijalno: x = 4/4 (potrosio sam prve dvije cetvorke), y = 4/4 (druge dvije cetvorke) i tada do beskonacnosti mogu raditi x, x+y, x+y+y, ... i generirati prirodne brojeve.

Ono, nisi precizno postavio zadatak.
 
Odgovor na temu

MilosSavic

Član broj: 61272
Poruke: 24
*.pat-pool.nsad.sbb.co.yu.



Profil

icon Re: Kako biste resili sledeci zadatak?22.06.2005. u 18:50 - pre 228 meseci

Evo razmisljaj lingvisticki... Imas gramatiku koja opisuje aritmeticki izraz (a koju sam vec negde gore naveo). Posto je to CF gramatika (kontekstno slobodna) problem odlucivosti za nju je veoma odluciv (da nije ne bi danas postojali kompajleri) te se svaki izraz moze izracunati. Problem je sada treba napraviti jednoznacno mapiranje izmedju reci te gramatike i skupa N. Azbuka koju imas na raspolaganju je {4, 4, 4, 4, {unarni operatori} {binarni operatori} {separatori}}. Posto je broj cetvorki konacan da bi napravio beskonacno mnogo reci treba da ponavljas beskonacno prebrojivo mnogo puta nesto iz {unarni operatori} {binarni operatori} {separatori}.. Posto separatori ne uticu na izraz, ostaju samo unarni i binarni operatori. Binarni operatori otpadaju jer tada moras imati beskonacno mnogo konstantnih operanda. I onda poenta cele price jeste u tom unarnom operatoru. Jer na primer ti mozes pisati
-4, -(-4), -(-(-4)))... i tako dalje, znaci beskonacno preborijivo mnogo reci. E sada, namerno nisam naveo sta moze i sme da se koristi pa je poenta da se vidi da mora da se koristi unarni operator ++ (ah pa matematika je tako divna SamoReferantnaSamoReproduktivnaSamoSebiDovoljna nauka). Napravis nulu (a to je trivijalno 4 - 4 + 4 - 4). Primenom unarnog operatora ++ mozes dobiti svaki broj iz N, a primenom unarnog operatora - od svakog iz N mozes dobiti svaki i iz Z *ali to nesto preterano i nije bitno jer su to skupovi iste kardinalnosti* Upravo to je i bila poenta: da se skonta znacaj unarnog operatora kada imas konacan broj operanda. Dve od tri funkcije koje sam pominjao iz Peanove aksiomatike su upravo te dve (Funkcija koja od argumenta pravi nulu i funkcija koji argument uvecava za jedan). Pored te dve postoji jos jedna funkcija koja se zove projekcija i koja ti vraca m-ti argument funkcije od njegovih n argumenata (ili ti m-ti clan liste koja ima n clanova). Te tri funkcije se zovu i primitivne. Iz primitivnih funkcija primenom pravila kompozocije, seme rekurzije i seme majorizacije *ma sta god to bilo* dobijas sve funkcije koje smo mi u sposobnosti da izracunamo. I TO JE KRAJ! NEMA DALJE, to je VRH DETERMINIZMA! I sada lepo ti das detetu koje je sedmi razred taj zadatak, pa ga malo mucis pa mu kasnije objasnis, ubijes ga u pojam jos dok je malo da se cisto ne zanosi kako je ovaj svet divan i lep :)

Druga stvar, ajde dozvolices mi jos malo da komentarisem tvoj program... Koliko sam ja skontao on ti pronalazi prvo najblize resenje koje upada u neki interval... Ono sto sam pokusavao da ti kazem u prethodnim mailovima jeste da je odrzavanje stabla zavisnosti potpuno nepotrebno (jer ono tebi predstavlja samo jednu medjuformu koja je krajnje nepotrebna ukoliko sam rezultat ne dajes kao stablo zavisnosti)... Zasto? Zato sto puno ljudi nikada ne razume kako stvarno radi rekurzija. Gde je problem? Problem je u tome sto nikada ne shvate da postoje tri stvari: odmotavanje rekurzije, trivijalni slucaj rekurzije da odmotavanje ne bude beskonacno i zamotavanje rekurzije. Upravo to zamotavanje, tu mogucnost da se vratite u neki tamo prethodni kontekst niko ne koristi. Gde je problem? Problem su nam nametnuli imperativni programski jezici koju nam razgradjuju intuiciju o programiranju kao o LINEARNOJ STVARI. Ali linearno to je nesto sto je daleko ispod REKURZIVNOG. Zasto linearno, to je posledica okoline u kojoj zivimo, tj. pre svega nase iluzije da vreme protice linearno i to po funkciji t := t + 1 *mada mi nikada necemo znati kako ono stvarno protice niti cemo ikada moci modelovati neki model u kome zaista mozemo simulirati nase prostor-vreme*. Tako se nama svaka instrukcija izvrsava tek kada se prethodna zavrsi, sto je na najnizem nivou zaista tako i kod rekurzije, ali ne i na visem nivou, gde preko tog mehanizma rekurzije mozemo da se setamo kruzno po nasem kontekstu, tj. nasem programerskom prostoru. E sada da preskocimo vise filozofiju i da se vratimo na program. Fora je da si koristio mogucnosti koje ti se nude u zamotavanju rekurzije mogao si fino da rekonstruises tvoj izraz ciju su vrednost naracunao u odmotavanju rekurzije. Evo na primer odradi neki trace tvoje rekurzivne funkcije i gledaj kako ti se menjaju parametri tih funkcija. Onda nacrtaj stablo zavisnosti medju funkcijama *tj, neka ti funkcije budu cvorovi, a linkujes ih povezanim linkom ukoliko je jedna funkcija pozivala drugu* i dobices jedno stablo koje ce veoma da lici na ono tvoje... E o toj duplikaciji sam pricao. Ili gledaj kako se cvorovi "umecu" i brisu iz tvog stabla. Isto onako kako se odmotava i zamotava rekurzija. Znaci da zavrsimo pricu oko toga: dinamika tvog rekurzivnog resenja bi trebala da izgleda ovako (zapisano u pseudo kodu - ala sam perverzan):
Code:

PROGRAM Dinamika Rekurzivnog Resenja

String Resenje = prazan;
VISE PUTA
        ODMOTVA SE REKURZIJA 
        TRIVIJALAN SLUCAJ (tada se vec zna vrednost izraza i da li je kriterujum     
                                    zadovoljen)
        AKO JE KRITERIJUM ZADOVOLJEN POSTAVI String Resenje na prazan
        ZAMOTAVA SE REKURZIJA
                UKOLIKO JE KRITERIJUM BIO ZADOVOLJEN
                        IZ LOKALNE OKOLINE (koju znas jer su to parametri rekurzivnih 
                        poziva iz dinamike odmotavanja rekurzije, a vraceni smo bas u taj
                        kontekst)
                                DOPISI LOKALNU OKOLINU U String Resenje NA NACIN 
                                KOJI JEDNOZNACNO DETERMINISE SAMA OKOLINA
END VISE PUTA
STAMPAJ String Resenje


I jos par stvari da napomenem da ne ostane nerazjasnjeno.
Heuristike nam sluze da pravimo brze algoritme koji rade sa nekom verovatnocom koja zavisi od same heuristike.
Asemblerski jezici sem mozda apstraktnih asemblera *kao sto je na primer troadresni medjukod* nisu strogo tipizirani kao sto sam vec rekao u pravom smislu te reci jer i nemaju tipove podataka, mada postoje razna ogranicenja u vezi operanada asemblerskih instrukcija po modovima adresiranja.
Ako nekoga slucajno vredjam mojim direktnim prozivanjem molim neka se ne oseca ugrozenim jer to je samo jedan specifican mehanizam koji sam naucio dugo godina igrajuci mafiju. Uostalom moje misljenje je samo jedno, tek onda kada prodje proces drustvene evolucije, kada dostigne jedan drustveni konsenzus, ted ga tada treba shvatati zdravo za gotovo. Do tada ne treba da se sekira.... A ta mafija je stvarno korisna stvar...

pozdravi Milos
 
Odgovor na temu

[KS]
Damir Kasipovic
Banjaluka

Član broj: 55395
Poruke: 46
*.dialup.blic.net.



Profil

icon Re: Kako biste resili sledeci zadatak?06.07.2005. u 23:47 - pre 228 meseci
(1^4+3)*6=24
Damir Kasipović
[email protected]
+387 (0)65 979 949
 
Odgovor na temu

tolstoy
Milan Ilich
Ukraine, Russia, Serbia

Član broj: 53619
Poruke: 111
*.irtelcom.ru.

ICQ: 225349472


+2 Profil

icon Re: Kako biste resili sledeci zadatak?14.07.2005. u 03:18 - pre 227 meseci
Citat:
[KS]: (1^4+3)*6=24


Covek rece da se koriste samo osnovne operacije ( +, -. *, / )
 
Odgovor na temu

[es] :: Art of Programming :: Kako biste resili sledeci zadatak?

[ Pregleda: 8154 | Odgovora: 17 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.