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
Ilość liczb z przedziału których suma cyfr jest równa x
-
- 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
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
Ilość liczb z przedziału których suma cyfr jest równa x
podejście siłowe
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ć
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ć
-
- 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
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ść.
Ilość liczb z przedziału których suma cyfr jest równa x
Masz tutaj liczbę i sumę cyfr. Nie widzisz żadnej zależności?
Ukryta treść: