Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
Altri Linguaggi - Piccolo quiz
Forum - Altri Linguaggi - Piccolo quiz

Avatar
sora101 (Normal User)
Newbie


Messaggi: 4
Iscritto: 29/08/2007

Segnala al moderatore
Postato alle 18:42
Sabato, 02/04/2011
Più o meno piccolo; un quiz che non riesco a risolvere, forse perchè non ho capito bene la domanda, forse perchè è difficile...lo posto in inglese:

Testo quotato

find all subsets of an array
    where the largest number is the sum of the remaining numbers.
    For example, for an input of:

    (1, 2, 3, 4, 6)

    the subsets would be

    1 + 2 = 3
    1 + 3 = 4
    2 + 4 = 6
    1 + 2 + 3 = 6



tradotto come l'ho capito:
Testo quotato


trova tutti gli insiemi di un'array dove il numero più largo è la somma dei numeri rimanenti. per esempio per l'input

(1, 2, 3, 4, 6)

    gli insiemi sarebbero

    1 + 2 = 3
    1 + 3 = 4
    2 + 4 = 6
    1 + 2 + 3 = 6



il testo non l'ho capito molto ma l'esempio aiuta un po... questo principio è da applicare alla seguente array:
3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99

per affrontare questo quesito ho usato il php e ho fatto questo script(terribile e complicato)
Codice sorgente - presumibilmente Plain Text

  1. <?php
  2. $ar=Array(3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99);
  3. $a=0;
  4. $x=Array(0);
  5. $c=0;
  6. $cmb=Array();
  7. echo "Getting combos...\n";
  8. while($a==0){
  9.         $r=Array();
  10.         for($i=0;$i<count($x);$i++){
  11.                 //echo $ar[$x[$i]];
  12.                 array_push($r,$ar[$x[$i]]);
  13.         }
  14.         //echo "\n";
  15.         smist($r);
  16.         $x[0]++;
  17.         for($k=0;$k<count($x);$k++){
  18.                 if($x[$k] == count($ar)){
  19.                         $x[$k]=0;
  20.                         if($k+1>=count($x)){
  21.                                 $x[$k+1]=0;
  22.                                 echo count($x)."\n";
  23.                         }else{
  24.                                 $x[$k+1]++;
  25.                         }
  26.                 }
  27.         }
  28.         if(count($x)>count($ar)){
  29.                 $a=1;
  30.         }
  31. }
  32. echo "Removing multiple usage...\n";
  33.  
  34. foreach($cmb as $kele=>$ele){
  35.         for($x=0;$x<count($ele);$x++){
  36.                 $c=0;
  37.                 for($y=0;$y<count($ele);$y++){
  38.                         if($ele[$x]==$ele[$y]){
  39.                                 $c++;
  40.                                 if($c>=2){
  41.                                         unset($cmb[$kele]);
  42.                                         $x=count($ele)+1;
  43.                                         $y=count($ele)+1;
  44.                                 }
  45.                         }
  46.                 }
  47.         }
  48. }
  49. $res=Array();
  50. echo "Making result...\n";
  51. foreach($cmb as $kele=>$ele){
  52.         $t=0;
  53.         for($x=0;$x<count($ele);$x++){
  54.                 $t +=$ele[$x];
  55.         }
  56.         $c=0;
  57.         for($x=0;$x<count($ar);$x++){
  58.                 if($t==$ar[$x] && in_array($ar[$x],$ele)==false){
  59.                         array_push($res,$ele);
  60.                 }
  61.         }
  62. }
  63. foreach($res as $re){
  64.         foreach($re as $r){
  65.                 echo $r." ";
  66.         }
  67.         echo "\n";
  68. }
  69.  
  70. function smist($r){
  71.         global $cmb;
  72.         $key="";
  73.         sort($r);
  74.         for($i=0;$i<count($r);$i++){
  75.                 $key .=$r[$i]."+";
  76.         }
  77.         if(count($r)>1){
  78.                 $cmb[$key]=$r;
  79.         }
  80. }
  81.  
  82. ?>



Per chi vuole evitare di cercare di capirlo segue queste operazioni:
-trova tutte le combinazioni degli elementi
-rimuove quelli dove ci sono numeri ripetuti
-mantiene solo quelli il cui risultato della somma di ogni combinazione sia un numero presente nell'array iniziale ma che non sia uno di quelli usati nella combinazione

inspiegabilmente funziona. Cioè, applicando il programma all'array 1,2,3,4,6 restituisce quegli insiemi.

Sorge un problema. 1,2,3,4,6 sono 5 elementi. poche combinazioni. L'array a cui applicare il codice sono 22. non so quante combinazioni. non voglio sapere.
quindi il mio programmino non è utilizzabile. ho pensato ci sia una qualce relazione tra quei numeri. ma non sono capace di trovarla. qualche anima pia che mi può dare una mano?

Posto qui perchè penso si possa fare in qualsiasi linguaggio...ciò che mi interessa è più la teoria....

GRAZIE!

PM