permutacje? kombinacje? php c++ excel - help needed .. Opcje

[pwsmile]

Witam i proszę o pomoc ..

nie mogę rozgryźć następującej sprawy..

mam dane :

- x liczb (np.5 liczb i np. takie : 1 2 3 4 5 , ale może być też: 1 3 3 5 5)

- sumę którą chcę otrzymać z dodania którychś (obojętnie ilu) z danych liczb (np. suma=11)

.. i potrzebuję program / skrypt / arkusz excel, który powie mi jak Abel krowie, które liczby ze zbioru muszą być dodane, żeby utworzyły sumę jaką chcę.

Dla zbioru: 1 2 3 4 5 i danej żądanej sumy 11 byłyby to następujące możliwości:

1_2_3___5 (suma: 11)
__2___4_5 (suma: 11)

Dla zbioru: 1 3 3 5 5 i danej żądanej sumy 11 są 3 możliwości:

__3_3_5__ (suma: 11)
__3_3___5 (suma: 11)
1_____5_5 (suma: 11)

Nie jest ważne ile z liczb podanych w zbiorze złoży się na podaną sumę, jednak każda kolejna z liczb w zbiorze powtarzać się może tylko 1 raz (np. pierwsza liczba w ostatnim przykładzie (1) może byż brana pod uwagę tylko raz, czyli rozwiązaniem nie może być

1_1_1_1_1_1_1_1_1_1_1 (bo liczba 1 w zbiorze wystepuje tylko raz)

ale

liczba 5 - też w drugim przykładzie - powtórzyć się może 2 razy, bo tyle razy wystepuje w zbiorze


Super optymalnie byłoby, gdyby programik w przypadku nie znalezienia pasujących składników dających szukaną sumę, podał najbliższą możliwą kombinację w górę i najbliższą możliwą w dół ..

.. np jezeli żądaną sumą byłaby liczba 2, to mając dany zbiór jak w przykładzie drugim: 1 3 3 5 5 program nie znajdzie wprawdzie odpowiednika, bo suma żadnych ze składników w tym zbiorze nie daje liczby 2, ale wypisze:

1________ (suma: 1, reszta 1)
__3______ (suma: 3, reszta -1)
____3____ (suma: 3, reszta -1)

podobnie dla szykanej sumy 12 i tego samego zbioru: 1 3 3 5 5 pasujący odpowiednik nie zostanie znaleziony, jednak najbliższymi dodatnimi i ujemnymi wartościami będą:

1_____5_5 (suma: 11, reszta 1)
1_3___5_5 (suma: 13, reszta -1)
1___3_5_5 (suma: 13, reszta -1)




Jeżeli ktoś ma jakiś pomysł, lub może już nad czymś takim myslał i ma gotowca, byłbym wdzięczny za udostępnienie.

Pozdrawiam
pwsmile

[piotrekkr]

z tym problemem to chyba raczej na matematyka.org permutacje komninacje itp mi tez to sie na studiach zaczelo :/

[jarrod]

[PHP] pobierz, plaintext 
<?php
function test($suma=null)
{
	if(!$suma) $suma = rand(0,45); // 45 ponieważ 9+9+9+9+9 = 45
	if($suma == 0) return 'Zbiór nie zawiera liczb ujemnych. Nie można wykonać działania.';
	elseif($suma == 1) return 'Suma == 1 zatem nie można wykonać działań.';
 
	$liczby[0] = rand(0,9);
	$liczby[1] = rand(0,9);
	$liczby[2] = rand(0,9);
	$liczby[3] = rand(0,9);
	$liczby[4] = rand(0,9);
	// posiadamy już pięć losowych liczb które mogą się powtarzać
 
	// dla porządku można je posortować
	sort($liczby);
 
 
	// sprawdzam czy suma wszystkich liczb jest większa od szukanej sumy
	// inaczej szykanie nie mam sensu
	if(array_sum($liczby) >= $suma) 
	{
		$breakAll = false; // kontrola wyników
		$nSuma = 0; // suma kontrolna
		$wynik = array(); // wynik działania funkcji
		$tmpKeys = array(); // tu przechowuję indexy liczb użytych w działaniu 
 
		// zaczynamy iterowanie po tablicy
		for($i=0; $i<5;$i++)
		{
 
			for($e=$i;$e<5;$e++)
			{
 
				$tmpKeys[] = $e;
				$nSuma += $liczby[$e];
 
				if($nSuma == $suma) // znaleziono pasujący wynik
				{
					$wyn = '';
					foreach($tmpKeys as $key)
					{
						$wyn .= $liczby[$key].'+';
					}
 
					$wyn = substr($wyn,0,strlen($wyn)-1);
					$wyn .= '='.$nSuma;
 
					$wynik['dokladnie'][] = $wyn;
 
					$nSuma = 0;
					$tmpKeys = array();
					break;
				}
				elseif($nSuma > $suma) // znaleziono pierwszy wyższy wynik
				{
					$wyn = '';
					foreach($tmpKeys as $key)
					{
						$wyn .= $liczby[$key].'+';
					}
					$wyn = substr($wyn,0,strlen($wyn)-1);
					$wyn .= '='.$nSuma;
					$resta = $suma-$nSuma;
 
					$wynik['wieksze'][] = array($wyn,$resta);
 
					$nSuma = 0;
					$tmpKeys = array();
					break;
				}
				elseif($e == 4) // ostatni element -> suma wszystkich pozostałych jest mniejsza od szukanej sumy
				{
					$breakAll = true;
 
					$wyn = '';
					foreach($tmpKeys as $key)
					{
						$wyn .= $liczby[$key].'+';
					}
					$wyn = substr($wyn,0,strlen($wyn)-1);
					$wyn .= '='.$nSuma;
					$resta = $suma-$nSuma;
 
					$wynik['mniejsze'][] = array($wyn,$resta);
 
					$nSuma = 0;
					$tmpKeys = array();
					break;
				}
			}
 
			if($breakAll) break;
 
		}
	}
	else
	{
		$wynik['max'] = array_sum($liczby);
	}
	$wynik['liczby'] = $liczby;
	$wynik['suma'] = $suma;
	return $wynik;
}
 
$wyniki = test();
 
$ret = 'Wynik działania programu:<br/>';
 
if(is_array($wyniki))
{
	$ret .= '<br/>Liczby w zbiorze: '.implode(',',$wyniki['liczby']);
	$ret .= '<br/>szukana suma: '.$wyniki['suma'].'<br/>';
 
	if(isset($wyniki['dokladnie']))
	{
		$ret .= '<br/>Dokładny wynik daje suma liczb:<br/>';
 
		foreach($wyniki['dokladnie'] as $wyn)
			$ret .= $wyn.'<br/>';
	}
	if(isset($wyniki['wieksze']))
	{
		$ret .= '<br/>Sumę minimalnie większą dają liczby:<br/>';
 
		foreach($wyniki['wieksze'] as $wyn)
			$ret .= $wyn[0].' reszty: '.$wyn[1].'<br/>';
	}
	if(isset($wyniki['mniejsze']))
	{
		$ret .= '<br/>Sumę minimalnie mniejszą dają liczby:<br/>';
 
		foreach($wyniki['mniejsze'] as $wyn)
			$ret .= $wyn[0].' pozostaje: '.$wyn[1].'<br/>';
	}
 
	if(isset($wyniki['max']))
	{
		$ret .= 'Suma wszyskich liczb zbioru ('.$wyniki['max'].') jest mniejsza od podanej sumy.';
	}
}
else
{
	$ret .= $wyniki;
}
echo $ret;
?>
[PHP] pobierz, plaintext 

uff

[pwsmile]

Dzięki piotrekkr, byłem na matematyka.org i nie do końca znalazłem jak to ugryźć.

.

Dla jarrod extra wieeeeelkie DANKE !

Przetestowałem skrypt i to jest exactly to o czym talking about

Masz u mnie flaszkę ..

Coś tylko jest w obliczeniach chyba jeszcze nie tak, bo wyniki się czasem nie zgadzają.

Wpisz prosze do bazy liczby 1 5 6 7 7 i daj szukanie sumy 21

Własnie mam to w wyniku kodu i wygląda to tak:


Wynik działania programu:

Liczby w zbiorze: 1,5,6,7,7
szukana suma: 21

Sumę minimalnie większą dają liczby:
1+5+6+7+7=26 reszty: -5
5+6+7+7=25 reszty: -4

Sumę minimalnie mniejszą dają liczby:
6+7+7=20 pozostaje: 1


.. czyli gdzieś się program machnął, bo 1+6+7+7 daje 21 bez reszty, a wynik nie podaje tej informacji

Podobnie (może przyczyna jest ta sama i jest to poprostu już konsekwencją owego błędu) podawane propozycje liczb minimalnie większych i mniejszych nie zawsze są zgodne z prawdą


Poza tym przerobiłem Twój kod podając moje konretne przykłady, w których pojawiają się ułamki z dwoma miejscami po przecinku (kropce), jak i podałem własną, faktycznie szukaną sumę. Załączam kod, ponieważ nie wiem czy zmieniając coś w tablicy, nie zmieniłem czegoś, czego nie powinienem.

[PHP] pobierz, plaintext 
<?php
function test($suma=null)
{
	if(!$suma) $suma = (251.16); // podana suma jest rzeczywistym szykanym wynikiem
	if($suma == 0) return 'Zbiór nie zawiera liczb ujemnych. Nie można wykonać działania.';
	elseif($suma == 1) return 'Suma == 1 zatem nie można wykonać działań.';
 
	$liczby[0] = (64.77);
	$liczby[1] = (52.59);
	$liczby[2] = (54.18);
	$liczby[3] = (42.55);
	$liczby[4] = (50.18);
	$liczby[5] = (52.59);
	$liczby[6] = (50.35);
	$liczby[7] = (51.88);
	$liczby[8] = (53.12);
	$liczby[9] = (49.15);
	$liczby[10] = (47.05);
	$liczby[11] = (52.83);
	$liczby[12] = (53.55);
	$liczby[13] = (52.96);
	$liczby[14] = (51.98);
 
 
 
	//
	// wpisałem własne liczby jako konkretny przykład
	//
 
 
 
	// dla porządku można je posortować
	sort($liczby);
 
 
	// sprawdzam czy suma wszystkich liczb jest większa od szukanej sumy
	// inaczej szykanie nie mam sensu
	if(array_sum($liczby) >= $suma) 
	{
		$breakAll = false; // kontrola wyników
		$nSuma = 0; // suma kontrolna
		$wynik = array(); // wynik działania funkcji
		$tmpKeys = array(); // tu przechowuję indexy liczb użytych w działaniu 
 
 
 
 
		// wartość końcową dla tablicy i pętli poniżej zmieniłem na <15 ale niestety nie jestem pewien czy to tak ma być
 
 
 
 
		// zaczynamy iterowanie po tablicy
		for($i=0; $i<15;$i++)
		{
 
			for($e=$i;$e<15;$e++)
			{
 
				$tmpKeys[] = $e;
				$nSuma += $liczby[$e];
 
				if($nSuma == $suma) // znaleziono pasujący wynik
				{
					$wyn = '';
					foreach($tmpKeys as $key)
					{
						$wyn .= $liczby[$key].'+';
					}
 
					$wyn = substr($wyn,0,strlen($wyn)-1);
					$wyn .= '='.$nSuma;
 
					$wynik['dokladnie'][] = $wyn;
 
					$nSuma = 0;
					$tmpKeys = array();
					break;
				}
				elseif($nSuma > $suma) // znaleziono pierwszy wyższy wynik
				{
					$wyn = '';
					foreach($tmpKeys as $key)
					{
						$wyn .= $liczby[$key].'+';
					}
					$wyn = substr($wyn,0,strlen($wyn)-1);
					$wyn .= '='.$nSuma;
					$resta = $suma-$nSuma;
 
					$wynik['wieksze'][] = array($wyn,$resta);
 
					$nSuma = 0;
					$tmpKeys = array();
					break;
				}
 
 
 
 
				// Poniżej zmieniłem 4 na 14, bo taki nr ma teraz ostatnia liczba, ale bardziej na
 intuicję niż wiedzę
 
 
 
 
				elseif($e == 14) // ostatni element -> suma wszystkich pozostałych jest mniejsza od szukanej sumy
				{
					$breakAll = true;
 
					$wyn = '';
					foreach($tmpKeys as $key)
					{
						$wyn .= $liczby[$key].'+';
					}
					$wyn = substr($wyn,0,strlen($wyn)-1);
					$wyn .= '='.$nSuma;
					$resta = $suma-$nSuma;
 
					$wynik['mniejsze'][] = array($wyn,$resta);
 
					$nSuma = 0;
					$tmpKeys = array();
					break;
				}
			}
 
			if($breakAll) break;
 
		}
	}
	else
	{
		$wynik['max'] = array_sum($liczby);
	}
	$wynik['liczby'] = $liczby;
	$wynik['suma'] = $suma;
	return $wynik;
}
 
$wyniki = test();
 
$ret = 'Wynik działania programu:<br/>';
 
if(is_array($wyniki))
{
	$ret .= '<br/>Liczby w zbiorze: '.implode(',',$wyniki['liczby']);
	$ret .= '<br/>szukana suma: '.$wyniki['suma'].'<br/>';
 
	if(isset($wyniki['dokladnie']))
	{
		$ret .= '<br/>Dokładny wynik daje suma liczb:<br/>';
 
		foreach($wyniki['dokladnie'] as $wyn)
			$ret .= $wyn.'<br/>';
	}
	if(isset($wyniki['wieksze']))
	{
		$ret .= '<br/>Sumę minimalnie większą dają liczby:<br/>';
 
		foreach($wyniki['wieksze'] as $wyn)
			$ret .= $wyn[0].' reszty: '.$wyn[1].'<br/>';
	}
	if(isset($wyniki['mniejsze']))
	{
		$ret .= '<br/>Sumę minimalnie mniejszą dają liczby:<br/>';
 
		foreach($wyniki['mniejsze'] as $wyn)
			$ret .= $wyn[0].' pozostaje: '.$wyn[1].'<br/>';
	}
 
	if(isset($wyniki['max']))
	{
		$ret .= 'Suma wszyskich liczb zbioru ('.$wyniki['max'].') jest mniejsza od podanej sumy.';
	}
}
else
{
	$ret .= $wyniki;
}
echo $ret;
?>
[PHP] pobierz, plaintext 

Jeszcze raz bardzo dziękuję za pomoc.

Jeżeli temat błędu w kodzie nie jest zawiły do poprawki i nie zniechęciłem Cię jeszcze, byłbym bardzo wdzięczny za korektę. Z importem albo ręcznym zaktualizowaniem danych w kodzie będę sobie już potem jakoś za każdym razem radził.

Pozdrawiam serdecznie
pwsmile :roll2:

[jarrod]

Dałem Ci ramy do stworzenia tego czego chcesz.
Brakuje tam warunków aby program działał pewniej. Widzisz, o godzinie 2 w nocy, mając na 9 rano do pracy, jakoś nie chciało mi się już dłużej nad tym siedzieć

Jesśli chodzi o warunki pętli to są prawidłowe. Szukasz do elemenu mniejszego od sumy elementów w tablicy (w tym przypadku można użyć również $i<= 14 co daje to samo). Inaczej pętla obiegnie tablice za mało razy i funkcja nie zadziała prawidłowo bo nie będzie iterować po wszystkich elementach a jak za dużo to niepotrzebnie wydłuzy się czas działania.

Poprawki wyglądają na prawidłowe.

Jeśli chcesz aby to pewniej działało to najlepiej narysuj sonie jak ta funkcja działa i wówczas będziesz widział jakie warunki należy dodać aby pokazywało dokładne wyniki.