[C++]Suma cyfr

[xml1]

Mam problem z optymalizacją czasową algorytmu znajdującego pośród zbioru \(\displaystyle{ \left\{ a,...,b\right\}}\) liczb, których suma cyfr jest równa \(\displaystyle{ s}\). Oczywiście \(\displaystyle{ a, b, s}\) są podane na wejściu. Zastanawiam się na przykład czy mogę przeszukiwać zbiór nie od a, lecz od s do b. Dla większych liczb poniższy algorytm jest poprostu za wolny:

Kod: Zaznacz cały

#include <iostream>
int suma(int liczba)
{
	int wynik = 0;
		while (liczba > 0)
		{
			wynik += liczba%10;
			liczba /= 10;
		}
		return wynik;
}

int main( )
{
	int n; std::cin >> n;
	int a, b, s, c=0;

	for(unsigned int i = 0 ; i < n ; i++)
	{
		std::cin >> a >> b >> s;
		if(a<b)
		{
			for(unsigned int i = a; i <=b; i++)
				if(suma(i) == s)
					c++;
		}
		std::cout << c << "
";
		c=0;
	}
	return 0;
}

[Mistrz]

Twój algorytm działa w czasie \(\displaystyle{ O((b-a) \log_{10 } b)}\). Jestem przekonany, że to zadanie można rozwiązać w czasie znacznie mniejszym, niż liniowy, ale nie wiem jak. Póki co widzę, jak można przyspieszyć Twoje rozwiązanie dziewięciokrotnie, czy to Ci wystarczy? I drugie pytanie: chcesz, żeby Ci podać rozwiązanie, czy żeby Cię na nie naprowadzić?

[xml1]

Póki co widzę, jak można przyspieszyć Twoje rozwiązanie dziewięciokrotnie, czy to Ci wystarczy?

Narazie tak, dalej będę szukał sam.

chcesz, żeby Ci podać rozwiązanie, czy żeby Cię na nie naprowadzić?

Oczywiście naprowadzić. Ewentualnie jeżeli problem jest skomplikowany, kawałek kodu do analizy.

[Mistrz]

Przez \(\displaystyle{ S(n)}\) rozumiem sumę cyfr liczby \(\displaystyle{ n}\). No to ile jest równe \(\displaystyle{ S(n+1)}\)? Dla wielu liczb prawdziwy jest wzór \(\displaystyle{ S(n+1) = S(n) + 1}\). Ale dla tych z '9' na końcu nie. Tak naprawdę, to niech \(\displaystyle{ n \in \mathbb{N}}\) oraz niech \(\displaystyle{ k}\) będzie liczbą końcowych dziewiątek liczby \(\displaystyle{ n}\) (na przykład dla \(\displaystyle{ n=9784599994599}\) mamy \(\displaystyle{ k=2}\)). Wówczas łatwo pokazać, że \(\displaystyle{ S(n+1) = S(n) + 1 - 9k}\).

Ogólnie, chodzi mi o to, że \(\displaystyle{ \bigwedge_{n \in \mathbb{N}}n - S(n)}\) jest podzielna przez \(\displaystyle{ 9}\). Potrafisz to uzasadnić? Potrafisz to wykorzystać w swoim algorytmie?

[xml1]

Zauważyłem, że \(\displaystyle{ \bigwedge_{n \in \mathbb{N}}n - S(n)}\) jest podzielne przez 9, zachodzi dla \(\displaystyle{ n \ge 10}\) oraz, że z równania \(\displaystyle{ S(n+1) = S(n) + 1 - 9k}\) można z powodzeniem ułożyć równanie rekurencyjne do użycia w programie. Nie wiem tylko jak efektywnie(czasowo) sprawdzać wartość k, danej liczby.

-- 25 sty 2012, o 13:06 --

Dodatkowo mam problemy z zaimplementowaniem tejże rekurencyjnej funkcji w programie. Mimo wszystko proszę o gotowy kod, żeby zobaczyć o co w rzeczywistości chodzi.

[Mistrz]

Dobrze uzasadniłeś, że \(\displaystyle{ n -S(n)}\) jest podzielne przez \(\displaystyle{ 9}\). Teraz jak to wykorzystać: zrób jakoś tak: \(\displaystyle{ d := s \mod 9; \\ e := a \mod 9; \\ \hbox{if } e>d \hbox{ then } d:= d+ 9; \\ a := a+d-e;}\)
mam nadzieję, że te 4 linijki podstawiają za \(\displaystyle{ a}\) najmniejszą liczbę co najmniej równą \(\displaystyle{ a}\) mającą tę samą resztę z dzielenia przez \(\displaystyle{ 9}\) co \(\displaystyle{ s}\).

Teraz w pętli nagłówek będzie

Kod: Zaznacz cały

for(i = a; i <= b; i += 9)

Rozumiesz?

[xml1]

Rozumiesz?

Umieszczone, ale potrzebuje, to jeszcze przyśpieszyć,

Dałem "pomógł" , bo pomogłeś mi w tym o co prosiłem, sam próbuje dalej szukać, ale niestety, bardzo potrzebuje większej optymalizacji czasowej, a brakuje mi jasnego pomysłu.-- 28 sty 2012, o 13:43 --Jest ktoś w stanie pomóc mi z optymalizacją tego? (code updated)