Ilość liczb z przedziału których suma cyfr jest równa x

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
snaf014
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 3 paź 2011, o 20:54
Płeć: Mężczyzna
Lokalizacja: podkarpackie
Podziękował: 1 raz

Ilość liczb z przedziału których suma cyfr jest równa x

Post autor: snaf014 »

Witam,
mam pytanie, czy istnieje jakiś ogólny sposób na rozwiązanie takiego zadania (chodzi o napisanie programu komputerowego rozwiązującego ten problem):

ile jest liczb z przedziału <a, b>, których suma cyfr jest równa x

Z góry dziękuję za odpowiedz
adampx
Użytkownik
Użytkownik
Posty: 158
Rejestracja: 4 mar 2009, o 09:21
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 1 raz
Pomógł: 29 razy

Ilość liczb z przedziału których suma cyfr jest równa x

Post autor: adampx »

Chyba dosyć prosty algorytm, jeśli wyjdziesz od tego, żeby szukaną liczbę zapisać jako dwa integery (dla liczb dwucyfrowych - osobno dla jendostek i dziesiątek). Wtedy możesz pętlą (a w zasadzie dwoma for'ami (dla dwucyfrówek!!)) przeszukać cały szukany obszar i zwrócić te potrzebne
Xitami

Ilość liczb z przedziału których suma cyfr jest równa x

Post autor: Xitami »

podejście siłowe

Kod: Zaznacz cały

int ile(int a, int b, int x){ // 0 < a <= b
	int n=0;
	while(a<=b){ 
		int k=a++, s=0;
		while( k ){
			s += k % 10;
			k /= 10; }
		if( s==x ) n++; }
	return n; }

1 - ile jest liczb o sumie cyfr równej "x" z przedziału <10^n, 10^(n+1)-1> np. 10...99 albo 100..999 ?
2 - ile takich z przedziału 10^n..k gdy k < 10^(n+1) np. 100..125 albo 1000..1413
z czymś takim można by dramatycznie przyśpieszyć
snaf014
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 3 paź 2011, o 20:54
Płeć: Mężczyzna
Lokalizacja: podkarpackie
Podziękował: 1 raz

Ilość liczb z przedziału których suma cyfr jest równa x

Post autor: snaf014 »

Dziękuję za odpowiedzi, ale wydaje mi się, że podejście siłowe tu nie zadziała. Podany przedział mogą zamykać bardzo wielkie liczby rzędu 10^100. Myślałem może, że jest jakiś stosunkowo łatwy sposób, aby wyliczyć ilość takich liczb ze wzoru lub znaleźć chociaż jakąś zależność.
abc666

Ilość liczb z przedziału których suma cyfr jest równa x

Post autor: abc666 »

Masz tutaj liczbę i sumę cyfr. Nie widzisz żadnej zależności?
Ukryta treść:    
ODPOWIEDZ