Pomoc - Szukaj - Użytkownicy - Kalendarz
Pełna wersja: [php]Suma liczb bez powtórzeń
Forum PHP.pl > Forum > Przedszkole
colachips
Witam,

Chciałbym dodać do siebie kilka liczb we wszystkich możliwych kombinacjach, ale żeby działania się nie powtarzały.. Pokaże kod jaki zrobiłem

  1.  
  2. $liczby = $_POST['liczby'];
  3.  
  4. for ($i = 1; $i <= count($liczby); $i++) {
  5. for ($j = 1; $j <= count($liczby); $j++) {
  6. echo 'Liczba '.$liczby[$i].' + Liczba '.$liczby[$j].' = '.($liczby[$i]+$liczby[$j]).'<br />';
  7. }
  8. }
  9.  


Problem w tym, że powtarza działania, czyli np.

$liczby[1] = 111;
$liczby[2] = 222;
$liczby[3] = 333;

W wyniku tego petla wyświetli:

Liczba 111 + Liczba 111 = 222 //ok
Liczba 111 + Liczba 222 = 333 //ok
Liczba 111 + Liczba 333 = 444 //ok
Liczba 222 + Liczba 111 = 333 //blad, ta kombinacja juz byla

Będę wdzieczny za naprowadzenie na właściwy trop
flashdev
takie coś:

  1. $liczby = array(1, 2, 3, 4);
  2.  
  3. for ($i = 0; $i < count($liczby); $i++) {
  4. for ($j = $i+1; $j < count($liczby); $j++) {
  5. echo 'Liczba '.$liczby[$i].' + Liczba '.$liczby[$j].' = '.($liczby[$i]+$liczby[$j]).'<br />';
  6. }
  7. }


Edit:
Widzę, że akceptujesz też 1+1
a wiec takie coś:

  1. $liczby = array(1, 2, 3, 4);
  2.  
  3. for ($i = 0; $i < count($liczby); $i++) {
  4. for ($j = $i; $j < count($liczby); $j++) {
  5. echo 'Liczba '.$liczby[$i].' + Liczba '.$liczby[$j].' = '.($liczby[$i]+$liczby[$j]).'<br />';
  6. }
  7. }
wookieb
Kiedyś to robiłem i działało to mniej więcej tak
  1. $tab = range(1,10);
  2. $ile = count($tab);
  3.  
  4. for($i=0; $i<$ile; $i++)
  5. {
  6. for($j = $i; $j<$ile; $j++)
  7. {
  8. echo $tab[$i].' + '.$tab[$j].' = '.($tab[$i]+$tab[$j])."\n";
  9. }
  10. }
colachips
u ~flashdev petla nie doda np. liczby[1] do liczby[1]
u ~wookieb doda
Obydwa przykłady pomogły. Dzięki!

// edit

Ok, wszystko było fajnie do momentu gdy chciałem rozszerzyć funkcjonalność tego skryptu aby wyświetlał faktycznie wszystkie kombinacje sum. Rozważmy przykład:

  1. $liczby = array(1, 2, 3, 4);
  2.  
  3. for ($i = 1; $i <= count($liczby); $i++) {
  4. for ($j = $i + 1; $j <= count($liczby); $j++) {
  5. $suma = $liczby[$i] + $liczby[$j];
  6. if (($suma % 1000) == 0) {
  7. $suma = '<span style="color: red">'.$suma.'</span>';
  8. }
  9. echo $liczby[$i].' + '.$liczby[$j].' = '.$suma.'<br />';
  10. for ($k = $j + 1; $k <= count($liczby); $k++) {
  11. $suma = $liczby[$i] + $liczby[$j] + $liczby[$k];
  12. if (($suma % 1000) == 0) {
  13. $suma = '<span style="color: red">'.$suma.'</span>';
  14. }
  15. echo $liczby[$i].' + '.$liczby[$j].' + '.$liczby[$k].' = '.$suma.'<br />';
  16. }
  17. }
  18. }


W wyniku pokaże się:

1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 4 = 7
1 + 3 = 4
1 + 3 + 4 = 8
1 + 4 = 5
2 + 3 = 5
2 + 3 + 4 = 9
2 + 4 = 6
3 + 4 = 7

Czyli brakuje kombinacji 1 + 2 + 3 + 4 = 10

A co jeśliby było 10 liczb? 10 pętli for? Musi być prostsze rozwiązanie..
wookieb
Nie. Musisz zauważyć pewne zależności przy kolejnych kombinacjach i odpowiednio je zrealizować. Ale powiedz do czego ci to potrzebne?
Nie wiem czy wyszło mi dobrze ale sprawdź
  1. $tab = range(1,6);
  2. $ile = count($tab);
  3.  
  4. $firstNumber = 0;
  5. $results = array();
  6.  
  7. while($firstNumber < $ile)
  8. {
  9. $rangeBegin = $firstNumber+1;
  10. $rangeEnd = $rangeBegin; // $firstNumber+1 :)
  11.  
  12. $results[] = $tab[$firstNumber].' + '.$tab[$firstNumber].' = '.($tab[$firstNumber]*2);
  13. while( !($rangeBegin==$rangeEnd && $rangeEnd == $ile) )
  14. {
  15. //zakres dodawanych liczb
  16. $rangeStr = '';
  17. $rangeSum = 0;
  18. for($i=$rangeBegin; $i<$rangeEnd; $i++)
  19. {
  20. $rangeStr .= ' + '.$tab[$i];
  21. $rangeSum += $tab[$i];
  22. }
  23.  
  24. // no i wynik
  25. for($c = $rangeEnd; $c<$ile ; $c++)
  26. {
  27. $results[] = $tab[$firstNumber].$rangeStr.' + '.$tab[$c].' = '.($tab[$firstNumber] + $tab[$c] + $rangeSum);
  28. }
  29.  
  30. // zmieniamy zakresy liczb dodawanych
  31. $rangeEnd++;
  32. if($rangeEnd >= $ile)
  33. {
  34. $rangeBegin++;
  35. if($rangeBegin >= $ile) break;
  36.  
  37. $rangeEnd = $rangeBegin + 1;
  38. }
  39. }
  40.  
  41. $firstNumber++;
  42. }
  43.  
  44. print_r($results);


Jeżeli coś nie pasuje to masz solidny początek, który możesz sobie zmodyfikować.
flashdev
proszę:

  1. $liczby = array(1, 2, 3, 4, 5, 6);
  2. $count = count($liczby);
  3. $vector = array();
  4. $res = array();
  5. for ($i = 0; $i < pow($count+1, $count); $i++) {
  6. $vector[0] = $i%($count+1);
  7. for( $j = 1; $j < $count; $j++ ){
  8. $vector[$j] = ($i - $vector[$j-1])/(pow(($count+1), $j))%($count+1);
  9. }
  10. $str = mkStr($vector, $liczby);
  11. if( !empty($str) ){
  12. $res[$i] = $str;
  13. }
  14. //echo $vector[0] . ' ' . $vector[1] . ' ' . $vector[2] . ' ' . $vector[3] . '<br />';
  15. }
  16.  
  17. echo '<pre>';
  18. echo '</pre>';
  19.  
  20. function mkStr(&$v, &$l){
  21. $count = count($v);
  22. $arr = array();
  23. $cnt = 0;
  24. for( $i = 0; $i < $count; $i++ ){
  25. if( $v[$i] != $count ){
  26. $arr[$cnt] = $l[$v[$i]];
  27. $cnt++;
  28. }
  29. }
  30. if( count($arr) > 1 ){
  31. sort($arr);
  32. return implode(' + ', $arr);
  33. }
  34. return '';
  35. }


Rozwiązanie nie jest zbyt dobrze napisane (bardzo obciąża komputer), ale jest najprostsze w implementacji jakie udało mi się wymyślić.
Prawdopodobnie jest to najgorsza z możliwych implementacji, ale za tą lepszą trzeba zapłacić smile.gif
Jedyna zaleta tego rozwiązania jest taka, że spełnia założenia.

@wookieb Twoje rozwiązanie zwraca 56 wyników dla 6 liczb, więc chyba zapomniałeś o "kilku" winksmiley.jpg
Zwróć uwagę na ogranicznik mojej pętli
  1. $i < pow($count+1, $count)

Tak, niestety jest to zależność potęgowa (x^x).
wookieb
Wiem, ale dałem mu taką podstawę z której będzie mógł kombinować resztę.

// EDIT Ponieważ miałem sporo błędów to postanowiłem, zrobić to zupełnie inaczej.
  1. // Skrypt tworzy możliwe kombinacje dodawania liczb. (bez powtarzania liczby w działaniu) metoda bitowa
  2. // np
  3. /*
  4.  1 + 2 = 3
  5.  1 + 3 = 4
  6.  1 + 4 = 5
  7.  1 + 2 + 3 = 6
  8.  1 + 2 + 4 = 7
  9.  itd
  10. */
  11. $tab = range(1,10);
  12. $ile = count($tab);
  13.  
  14. $num = str_repeat('1', $ile);
  15. $num = bindec($num); // mamy (prawie) wyliczoną liczbę możliwych kombinacji
  16.  
  17. $tmpNum = $num;
  18. $results = array();
  19.  
  20. while($tmpNum > 0)
  21. {
  22. // zeby errorow nie bylo
  23. $tmpNumStr = str_pad(decbin($tmpNum), $ile, '0', STR_PAD_LEFT);
  24.  
  25. $sum = 0;
  26. $sumStr = '';
  27. $numsAdded = 0;
  28.  
  29. for($i=0; $i<$ile; $i++)
  30. {
  31. // czy wstawic liczbe
  32. if($tmpNumStr[$i] == '1')
  33. {
  34. $sum+= $tab[$i];
  35. $sumStr.=' + '.$tab[$i];
  36. $numsAdded++;
  37. }
  38. }
  39. // jezeli tylko jedna liczba to nie jest to działanie
  40. if($numsAdded>1)
  41. {
  42. $results[] = substr($sumStr, 3).' = '.$sum;
  43. }
  44.  
  45. $tmpNum --;
  46. }
  47. print_r($results);
colachips
Imponujące! Muszę jeszcze zrozumieć JAK to wszystko działa.. sciana.gif Kiedy pojmę to dam znać. Dzieki za pomoc!
wookieb
Zapis bitowy ( dwójkowy) liczby pokazuje nam jakie liczby mamy wziąć do działania.
W zapisie bitowym liczby wyglądają np tak
1) 0001
2) 0010
3) 0011
4) 0100
5) 0101
6) 0110
7) 0111
...
Mamy teraz twoje liczby 1,2,3,4. Podstawmy twoje liczby na odpowiednie pozycje. Z pozycji gdzie jest 1 pobieramy odpowiadającą jej (pozycji) liczbę i wstawiamy do działania. Jeżeli w całym ciągu, jest tylko jedna 1 to olewamy

Przykład:
Kod
      1 | 2 | 3 | 4  | wynik
     -----------------
1)  - 0 | 0 | 0 | 1  | ------
2)  - 0 | 0 | 1 | 0  | ------
3)  - 0 | 0 | 1 | 1  | 3 + 4 = 7
4)  - 0 | 1 | 0 | 0  | ------
5)  - 0 | 1 | 0 | 1  | 2 + 4 = 6
6)  - 0 | 1 | 1 | 0  | 2 + 3 = 5
7)  - 0 | 1 | 1 | 1  | 2 + 3 + 4 = 9
8)  - 1 | 0 | 0 | 0  | ------
9)  - 1 | 0 | 0 | 1  | 1 + 4 = 5
10) - 1 | 0 | 1 | 0  | 1 + 3 = 4
11) - 1 | 0 | 1 | 1  | 1 + 3 + 4 = 8
12) - 1 | 1 | 0 | 0  | 1 + 2 = 3
13) - 1 | 1 | 0 | 1  | 1 + 2 + 4 = 7
14) - 1 | 1 | 1 | 0  | 1 + 2 + 3 = 6
15) - 1 | 1 | 1 | 1  | 1 + 2 + 3 + 4 = 10 (dlatego na początku wstawiłem same 1 do ciągu i przeliczyłem na system dziesięty, przez co otrzymałem liczbę potrzebnych operacji. od tej wartości odejmiemy ilość liczb jakie mamy i otrzymujemy liczbę możliwych kombinacji (u nas 15 - 4 = 11) )
flashdev
Cytat(wookieb @ 11.09.2009, 14:11:29 ) *
Zapis bitowy ( dwójkowy) liczby pokazuje nam jakie liczby mamy wziąć do działania.
W zapisie bitowym liczby wyglądają np tak
1) 0001
2) 0010
3) 0011
4) 0100
5) 0101
6) 0110
7) 0111
...


Pomijasz jeden mały szczegół:

Cytat(colachips @ 10.09.2009, 23:16:52 ) *
u ~flashdev petla nie doda np. liczby[1] do liczby[1]
u ~wookieb doda
Obydwa przykłady pomogły. Dzięki!

wookieb
A co za problem zrobić to poza pętlą? Albo nawet w niej
Kod
if($numsAdded>1)
{

}
else
{
// dodaj te same liczby
}

Z przykładu nie wynikało, że chciał takie działanie, więc może zmienił zdanie.
flashdev
Cytat(wookieb @ 11.09.2009, 14:25:45 ) *
A co za problem zrobić to poza pętlą? Albo nawet w niej
Kod
if($numsAdded>1)
{

}
else
{
// dodaj te same liczby
}

Z przykładu nie wynikało, że chciał takie działanie, więc może zmienił zdanie.


Jakie to proste smile.gif

A jak z tablicy 1, 2, 3 zrobisz:
1 + 1 + 2?
winksmiley.jpg
wookieb
Nie wiem czy zauwazyłeś ale z przykładu autor nie brał takiej kombinacji pod uwagę.. Ani nawet 1 + 1.
To jest wersja lo-fi głównej zawartości. Aby zobaczyć pełną wersję z większą zawartością, obrazkami i formatowaniem proszę kliknij tutaj.
Invision Power Board © 2001-2025 Invision Power Services, Inc.