Difference between revisions of "Clasele 11-12 lecția 33 - 10 iun 2015"

From Algopedia
Jump to: navigation, search
(Inițializare leneșă)
 
(No difference)

Latest revision as of 13:17, 9 June 2015

Puzzle-uri de logică

Multe din aceste puzzle-uri provin de pe trei site-uri pe care le urmăresc:

Probleme cu cântăriri

Ne interesează aceste probleme deoarece rezolvarea lor se leagă de complexitatea sortării în modelul bazat pe arbori de decizie.

În toate problemele dispunem de o balanță cu două talere. Când compară două greutăți A și B, această balanță dă unul din trei răspunsuri posibile: A > B, A = B sau A < B.

9 bile, 2 cântăriri

Se dau 9 bile identice ca formă, din care una este mai ușoară. Cum o aflăm din două cântăriri?

12 bile, 3 cântăriri

Se dau 12 bile identice ca formă, din care una este diferită (mai ușoară sau mai grea). Cum o aflăm din trei cântăriri?

  • Observație despre 13 bile și limitele modelului teoretic

6 bile (3+3)

Se dau 6 bile identice ca formă, din care 3 cântăresc 99 g și 3 cântăresc 100 g. Cum le diferențiem printr-un număr minim de cântăriri?

6 bile de 3 culori

Se dau 6 bile: două roșii, două galbene și două verzi. Din fiecare pereche, una cântărește 99 g, iar cealaltă 100 g. Cum le diferențiem printr-un număr minim de cântăriri?

Probleme cu fesuri și tricouri

În toate problemele de mai jos, prizonierii pot stabili o strategie comună înainte ca experimentul să înceapă.

10 prizonieri în linie

10 prizonieri sunt așezați în linie astfel încât fiecare prizonier îi poate vedea pe cei din fața lui. Gardianul le pune pe cap câte un fes roșu sau alb, la întâmplare. Începând cu ultimul prizonier, îi întreabă pe fiecare ce culoare are fesul lui. Dacă prizonierul ghicește este eliberat, altfel este executat. Apoi gardianul trece la următorul prizonier. Câți prizonieri se pot salva?

  • Generalizare: Dar dacă există N prizonieri și K culori de fesuri?

Pitici 1

Un spiriduș rău capturează N pitici. El așază pe capul fiecăruia un fes cu un număr între 1 și K. (Numerele nu sunt neapărat unice). Fiecare pitic poate vedea fesurile celorlalți pitici, dar nu și pe al său însuși. Apoi, toți piticii trebuie să anunțe simultan numărul pe care cred că îl au pe cap. Dacă cel puțin unul dintre ei ghicește, toți sunt eliberați. Cum procedează?

Pitici 2

Un spiriduș rău capturează N pitici și îi închide într-o peșteră complet întunecată. El pune pe capul fiecăruia un fes alb sau roșu, la întâmplare. Apoi, unul câte unul, piticii ies din peșteră pe poiana din față și trebuie să se separe în două grupe, conform culorilor fesurilor. Ei nu pot vorbi. Prin „separare” înțelegem că există o dreaptă care taie poiana astfel încât toți piticii cu fesuri albe să se afle de o parte a dreptei, iar cei cu fesuri roșii de cealaltă parte.

Safire și rubine

Un împărat vrea să-și testeze Sfatul celor 12 înțelepți. El pregătește 12 sipete dispuse într-un cerc. În fiecare sipet se află fie un safir, fie un rubin. Apoi, înțelepții intră în cameră și se așază fiecare în fața unui sipet. Înțelepții deschid sipetele astfel încât fiecare poate vedea piatra din celelalte sipete, dar nu și din al lui. Împăratul spune „cei care aveți rubine, veniți la mine”. Nu se ridică nimeni. Împăratul repetă întrebarea la fiecare 10 minute, timp de o oră. După o oră, un număr de înțelepți s-au ridicat și au venit la el. Desigur, toți au avut dreptate, iar toți cei care au rămas așezați aveau safire. Cum au judecat ei și câte rubine erau?

Convenția logicienilor

(Foarte asemănătoare cu problema precedentă). La o convenție a logicienilor, organizatorii le propun următorul joc. Le pun pe cap benzi de diferite culori (există o mare varietate de culori). Apoi îi așază într-un cerc. Apoi, în mod repetat, le cer să-și ghicească culoarea benzii. Configurația benzilor este de așa natură încât fiecare logician poate rezolva problema doar prin logică. Cum procedează?

Culoarea fesului probabilistic

Un gardian așază pe capetele a trei prizonieri câte un fes alb sau roșu, la întâmplare. Apoi, simultan, prizonierii trebuie să anunțe culoarea fesului lor, sau se pot abține. Ei sunt eliberați dacă cel puțin un prizonier și-a anunțat culoarea corectă și niciun prizonier nu a anunțat o culoare greșită. Ce strategie adoptă ei pentru a avea șanse cât mai mari de eliberare?

Culori alternante

(Greu)

Fie N prieteni. Ei se cunosc între ei și se pot distinge unul de altul. Ei primesc pe cap fesuri cu numere reale, toate distincte. Fiecare om vede fesurile prietenilor lui, dar nu și pe al lui însuși. Apoi, sunt duși în camere separate și sunt invitați să aleagă câte un tricou alb sau negru. La final, sunt readuși într-o cameră comună și sunt aranjați în ordinea numerelor de pe fes. Scopul este ca, în urma aranjării, tricourile să alterneze alb-negru-alb-negru... Ce strategie adoptă ei?

Probleme de programare

Programul care se autotipărește

Scrieți un program care se autotipărește, adică, la executare, tipărește exact codul-sursă. El nu are voie să deschidă fișiere.

f(f(x)) = -1

Există sau nu în C o funcție int f(int x) { ... } cu proprietatea că f(f(x)) = -x pentru orice x întreg?

Inițializare leneșă

Dați un algoritm care inițializează un vector în timp constant cu o valoare dată X. Cu alte cuvinte, orice apel care încearcă să citească al k-lea element, care încă nu a fost inițializat, trebuie să primească valoarea X. Inițializarea trebuie să funcționeze în O(1), dar algoritmul poate folosi memorie suplimentară.

Probleme de algoritmică

  • G11 Truchet tilings (programare dinamică)
  • G14 Josephus problem (baza 2)
  • G36 Average salary
    • zero knowledge proofs; exemple
  • G46 Number guessing game I
  • G46 Number guessing game II (algoritmi randomizați)
  • OCF 3-bit sensors (codificări)