Na ile sposobów można rozmienić 5000zł?

[djszaman]

Na ile sposobów można rozmienić 5000 zł za pomocą monet 1, 2, 3, 5 i 10 złotowych?

Bardzo bym prosił o pomoc w rozwiązaniu-- 14 paź 2010, o 16:25 --Próbowałem rozwiązać to zadanie przy pomocy funkcji tworzących, znalazłem pomoc na - zadanie 1.

Jednak w tym przypadku stworzenie tabelki takiej jak na ważniaku wymagałoby ode mnie wypełnienie wypełnienie co 1 kolumn od 1 do 5000. Mógłbym skorzystać z excela, ale muszę to zrobić ręcznie, więc może ktoś zna inny sposób?

[test30]

tutaj programy realizujace to dla monet 1, 2, 5.

Kod: Zaznacz cały

https://ideone.com/NudHY

Kod: Zaznacz cały

https://ideone.com/9F9zh

tutaj twoj problem w c++
https://ideone.com/oqEVl
ogolnie:
a_n=1 //na ile sposobow mozna rozmienic uzywac zlotowek
b_n=b_{n-2}+a_{n-1} \na ile sposoboe mozna rozmienic n zlotych uzywajac zlotowek i dwuzlotowek
c_n=c_{n-3}+b_{n} // -||- zlotowek, dwuzlotowek i pieciozlotowek
d_n=d_{n-5}+c_n // na ile -||- zlotowek, dwuzlotowek, trzyzlotowek i pieciozlotowek
e_n=e_{n-10}+d_n // na ile -||- zlotowek, dwuzlotowek, trzyzlotowek, pieciozlotowek, dyszek

[Xitami]

Kod: Zaznacz cały

http://pari.math.u-bordeaux.fr/

polcoeff(sum(i=0,5000,x^i)*sum(i=0,2500,x^(2*i))*sum(i=0,1667,x^(3*i))*sum(i=0,1000,x^(i*5))*sum(i=0,500,x^(i*10)),5000)
time = 17,797 ms.
%1 = 87536780112
wynik jest większy niż 2^32
W "ręczne" policzenie raczej nie wierzę.

\(\displaystyle{ 87536780112x^{5000}+87466918000x^{4999}+87397098139x^{4998}+87327319861x^{4997}+87257583500x^{4996}+87187888889x^{4995}+
87118235861x^{4994}+87048624750x^{4993}+86979055389x^{4992}+86909527611x^{4991}+86840041750x^{4990}+\\
\dots+\\21x^{10}+16x^{9}+13x^{8}+10x^{7}+8x^{6}+6x^{5}+4x^{4}+3x^{3}+2x^{2}+x+1}\)

Jeżeli dodamy jeszcze banknoty o nominałach 20, 50, 100, 200 wtedy liczba możliwości wzrasta do 2'184'511'626'666'001
sprawniej można policzyć to np. tak:

Kod: Zaznacz cały

#include <stdio.h>
typedef unsigned long long int uint;
#define N 5000

void zero(uint * w){
	int i;
	for(i=0;i<=N;i++) w[i]=0;
}
	
void conv(uint * w, uint * a, uint * b){
	int i,j;
	zero(w);
	for(i=0; i<=N; i++)
		for(j=0; j<=N-i; j++)
			w[i+j]+=a[i]*b[j];
}
uint w[N+1], a[N+1], b[N+1];
int main(){
	int i;
	for(i=0;i<=N;i++) a[i]=1;
	zero(b);
	for(i=0;i<=N/2;i++) b[2*i]=1;
	conv(w, a, b);
	zero(b);
	for(i=0;i<=N/5;i++) b[5*i]=1;
	conv(a,w,b);
	zero(b);
	for(i=0;i<=N/10;i++) b[10*i]=1;
	conv(w,a,b);
	zero(b);
	for(i=0;i<=N/3;i++) b[3*i]=1;
	conv(a,w,b);
	printf("%llu\n",a[N]);
	for(i=10;i>=0;i--)
		printf("%llu ",a[i]);
	return 0;
}

0.18 sekundy

[lkoikm]

Firma Nokia Solutions and Networks zorganizowała konkurs z podobnym (nieco trudniejszym)
zadaniem:

Na ile sposobów można rozmienić banknot 1024 N$N na nominały o mniejszej wartości należące do
zbioru {2i} N$N, gdzie i = 0,1,2,…,9?

więcej info na:

Mam nadzieję, że zainteresuje Was ta zagadka. Powodzenia!