Newsgroup: it.comp.programmare
Titolo: [ALGORITMI] Indovinello delle mille finestre

Ciao a tutti!
La mia ragazza mi ha proposto questo indovinello, pescato in un sito:
Ci sono mille finestre, tutte chiuse. Il sultano ha mille schiavi. Al
primo schiavo dice di aprire tutte le finestre. Al secondo schiavo
dice di chiudere tutte le seconde finestre (le multiple di 2) aperte e
aprire tutte le seconde finestre chiuse. Al terzo schiavo dice di
chiudere tutte le terze finestre aperte ed aprire tutte le terze
finestre chiuse. E così via fino al millesimo schiavo.
Io ho risolto con questo algoritmo:
Per i = 1 finchè i <= 1000
{
    Per j = i finchè j <= 1000
    {
        Se finestra[j] è chiusa: Apri Finestra[j]
        Altrimenti: Chiudi Finestra[j]
        j = j + i
    }
    i = i + 1
}
l'algoritmo dovrebbe essere formalmente corretto, ma secondo me si può
fare di meglio, aumentando drasticamente le prestazioni, ma non riesco
ad immaginare come.
Voi che ne dite? C'è qualcuno ce ha già sentito questo indovinello?
Grazie
LoneHawk

PS: Alla fine si vuole sapere quante sono le finestre aperte :D

Non è il classico problema da risolvere con la concorrenza ?
finestra = risorsa con 2 metodi sincronizzati (apri e chiudi )
1000 thread che svolgono il lavoro dei 1000 schiavi .
ciao
PP

 ad immaginare come.
Secondo me no, bisogna per forza fare 1000 x 1000 cicli perchč č il
problema stesso che lo richiede.
In pascal sarebbe qualcosa del genere:
var
    finestra: array[1..1000] of boolean;
    n, schiavo: integer;
begin
    for n := 1 to 1000 do finestra[n] := false; {chiude tutte le finestre}
    for schiavo := 1 to 1000 do
    begin
        n := 0;
        while true do
        begin
            n := n + schiavo;
            if n > 1000 then break;
            finestra[n] := not finestra[n];
        end;
    end;
end;
E queste le finestre aperte alla fine:
1
4
9
16
25
36
49
64
81
100
121
144
169
196
225
256
289
324
361
400
441
484
529
576
625
676
729
784
841
900
961
-- 
This is my useless sign.

problema stesso che lo richiede.
Già l'algoritmo proposto dall'OP fa MENO di 1000 x 1000 cicli. Ma è molto
probabile che si possa ancora migliorare.
Non c'è bisogno di eseguire 1000 cicli per sapere che il secondo schiavo
troverà aperte tutte le finestre pari, e quindi il terzo chiuse tutte le
finestre multiple di 6 e aperte le altre multiple di 3 (perché dispari).
Sono convinto che uno che abbia una maggior familiarità con il calcolo
modulare di quanta ne abbia io (e non ci vuole molto), potrebbe procedere
oltre, e arrivare a calcolare il risultato finale senza fare mille cicli.
Ciao.

E queste le finestre aperte alla fine:

Mi pare che le differenze prime siano illuminanti:
     F(n)  F(n+1)-F(n)    
     ---   ---------
       1  
       4        3
       9        5
      16        7
      25        9
      36       11
      49       13
      64       15
      81       17
     100       19
     121       21
     144       23
     169       25
     196       27
     225       29
     256       31
     289       33
     324       35
     361       37
     400       39
     441       41
     484       43
     529       45
     576       47
     625       49
     676       51
     729       53
     784       55
     841       57
     900       59
     961       61
Che cosa in particolare illuminino, io non saprei dire, ma immagino che
qualcuno più competente di me potrebbe ricavarne qualcosa di buono.
Ciao.


In PHP:
<?php
$finestre = array();
for ($n = 0; $n < 1000; $n++) {
    $finestre[$n] = 0;
}
$i = $k = 0;
for ($schiavo = 0; $schiavo < 1000; $schiavo++) {
    for ($n = 0; $n < 1000; $n++) {
        $i++;
        if ($n < $schiavo) {
            continue;
        }
        if ((($n+1) % ($schiavo+1)) == 0) {
            $k++;
            $finestre[$n] = ($finestre[$n]) ? 0 : 1;
        }
    }
}
foreach($finestre as $numero=>$stato) {
    if ($stato) {
        $aperte[] = $numero + 1;
    }
}
print_r($aperte);
echo "Cicli: $i\n";
echo "Controlli: $k\n";
?>
Output:
$ php -f php
Array
(
    [0] => 1
    [1] => 4
    [2] => 9
    [3] => 16
    [4] => 25
    [5] => 36
    [6] => 49
    [7] => 64
    [8] => 81
    [9] => 100
    [10] => 121
    [11] => 144
    [12] => 169
    [13] => 196
    [14] => 225
    [15] => 256
    [16] => 289
    [17] => 324
    [18] => 361
    [19] => 400
    [20] => 441
    [21] => 484
    [22] => 529
    [23] => 576
    [24] => 625
    [25] => 676
    [26] => 729
    [27] => 784
    [28] => 841
    [29] => 900
    [30] => 961
)
Cicli: 1000000
Controlli: 7069
$
MTC,
David
-- 
         Linux Registered User #334216
Get FireFox! >> 
http://snipurl.com/gofoxygo/
 <<
Blog         >>  
http://www.hanskalabs.net/
  <<
Staff        >> 
http://www.debianizzati.org/
 <<

 $
Saluti,


(riprendendo l'algoritmo dell'OP...)
L'algoritmo dell'OP è, mi pare:
   for ($schiavo = 0; $schiavo < 1000; $schiavo++) {
       for ($n = $schiavo; $n < 1000; $n += $schiavo) {
           $i++;
           ...
       }
   }
Ciao.

Grazie a tutti per le risposte.
Effettivamente avevo già sviluppato l'algoritmo in C# (linguaggio
scelto perchè era quello a tiro di tastiera, di fatti
l'implementazione non cambia, al netto delle sintassi).
Girottando per Google ho trovato che comunque la soluzione alla
domanda (quante sono le finestre aperte, una volta che tutti gli
schiavi abbiano terminato il proprio turno) è la radice quadrata del
numero arrotondata al numero più basso.
La spiegazione (in inglese e comunque poco chiara) l'ho trovata qui:
http://www.people.fas.harvard.edu/~hchong/puzz4sol.html
Effettivamente è esattamente il numero dei quadrati, intesi come N = a
* a, che esistono all'interno del sottoinsieme dei numeri naturali
presi in esame (in questo caso qualunque n compreso tra 1 e 1000).
L'unica risposta che non condivido è quella che propone l'utilizzo di
1000 threads, in quanto non è richiesta la concorrenzialità di accesso
alle finestre (ogni schiavo ha il suo turno). Inoltre all'aumento del
numero di finestre, aumentano anche le risorse (in termini di stack)
necessarie all'algoritmo, senza un significativo aumento delle
prestazioni rispetto all'algoritmo proposto (infatti ogni processo
dovrà attendere comunque che la risorsa "finestra" venga liberata dal
processo che la detiene, impiegando così del tempo prezioso per
valutare se la risorsa è libera e attendere che venga liberata). Senza
menzionare la difficoltà di implementare un sistema che valuti se una
finestra è accessibile e, in caso negativo, passi alla successiva,
ricordandosi tutte le finestre che ha saltato.
Grazie comunque a tutti :D
Lone

 Mi pare che le differenze prime siano illuminanti:
Intendi dire che le differenze sono numeri primi ?
Perché non lo sono... vedi 9, 15, 21, 25... ecc...
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

Perché non lo sono... vedi 9, 15, 21, 25... ecc...
Intendo dire che le differenze prime seguono una regola evidente e molto
semplice, in particolare sono i primi 30 numeri dispari.
Si vede ancor meglio passando alle differenze seconde:
     F(n)   Delta   Delta^2
     ----   -----   -------
      1
      4       3
      9       5        2
     16       7        2
     25       9        2
     36      11        2
     49      13        2
     64      15        2
     81      17        2
    100      19        2
    121      21        2
    144      23        2
    169      25        2
    196      27        2
    225      29        2
    256      31        2
    289      33        2
    324      35        2
    361      37        2
    400      39        2
    441      41        2
    484      43        2
    529      45        2
    576      47        2
    625      49        2
    676      51        2
    729      53        2
    784      55        2
    841      57        2
    900      59        2
    961      61        2
Che cosa si possa ricavare da questo non lo so (l'infarinatura di calcolo
alle differenze finite in mio possesso piů che tanto non mi consente), ma
mi pare impossibile che non se ne possa ricavare qualcosa.
Ciao.

 Voi che ne dite? C'è qualcuno ce ha già sentito questo indovinello?
Bello! Inizialmente mi hai fregato perchè NON dicevi qual'era alla fine 
la domanda (bastardooooo!!) ma è evidente che devi implementare una 
variante del crivello di Eratostene.
E' semplice: ogni schiavo è un numero divisore e fa il NOT logico della 
finestra divisibile per lui.
Perciò: i numeri primi avranno tutte finestre chiuse (divisibili per UNO 
  e per se stessi), i numeri composti da due fattori avranno finestre 
aperte (tre schiavi opereranno su di esse) ecc. ecc.: in definitiva, 
tutti i numeri composti da un numero di fattori DISPARI (contando anche 
l'unità) avranno finestre chiuse, e tutti gli altri le avranno aperte.
:-)


Quasi :D
In realtà, nel crivello di Eratostene ogni "finestra" i-esima con i
non primo viene eliminata e poi mai più modificata (non è che un
successivo passaggio su un numero già eliminato lo faccia tornare in
gara).
Non ho capito poi se con "fattori" includi anche l'1 oppure no O.o" In
questo caso il tuo ragionamento fila :D
Comunque anche con questa considerazione, e usando un algoritmo che
per ogni N <= 1000 conti i suoi divisori e, se questi sono dispari,
setti la finestra N-ESIMA aperta, la complessità computazionale
dell'algoritmo non cambia (è sempre un ciclo da 1 a N innestato in un
ciclo da 1 a 1000).
Pare che l'algoritmo più efficiente sia "sapere" che il risultato è la
parte intera della radice quadrata del numero di finestre :\