sora101 (Normal User)
Newbie
Messaggi: 4
Iscritto: 29/08/2007
|
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:
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:
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 |
<?php
$ar=Array(3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99);
$a=0;
$x=Array(0);
$c=0;
$cmb=Array();
echo "Getting combos...\n";
while($a==0){
$r=Array();
for($i=0;$i<count($x);$i++){
//echo $ar[$x[$i]];
array_push($r,$ar[$x[$i]]);
}
//echo "\n";
smist($r);
$x[0]++;
for($k=0;$k<count($x);$k++){
if($x[$k] == count($ar)){
$x[$k]=0;
if($k+1>=count($x)){
$x[$k+1]=0;
echo count($x)."\n";
}else{
$x[$k+1]++;
}
}
}
if(count($x)>count($ar)){
$a=1;
}
}
echo "Removing multiple usage...\n";
foreach($cmb as $kele=>$ele){
for($x=0;$x<count($ele);$x++){
$c=0;
for($y=0;$y<count($ele);$y++){
if($ele[$x]==$ele[$y]){
$c++;
if($c>=2){
unset($cmb[$kele]);
$x=count($ele)+1;
$y=count($ele)+1;
}
}
}
}
}
$res=Array();
echo "Making result...\n";
foreach($cmb as $kele=>$ele){
$t=0;
for($x=0;$x<count($ele);$x++){
$t +=$ele[$x];
}
$c=0;
for($x=0;$x<count($ar);$x++){
if($t==$ar[$x] && in_array($ar[$x],$ele)==false){
array_push($res,$ele);
}
}
}
foreach($res as $re){
foreach($re as $r){
echo $r." ";
}
echo "\n";
}
function smist($r){
global $cmb;
$key="";
sort($r);
for($i=0;$i<count($r);$i++){
$key .=$r[$i]."+";
}
if(count($r)>1){
$cmb[$key]=$r;
}
}
?>
|
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!
|
