Jak najsensowniej zrobić zapis "123 - 1^2 + 2^2 + 3^2"?

Cześć,

jak najsensowniej zrobić zapis

123 --> 1^2 + 2^2 + 3^2?

Chodzi o to, że na wejściu mamy liczbę np. 123 i trzeba ją zapisać jako 1^2 + 2^2 + 3^2 i policzyć sumę, czyli 1+4+9 = 14, potem robimy zapis 14 --> 1^2+4^2=1+16=17 i zapisujemy 17 jako 1^2+7^2 itd.
Potem poszukać minimalnej liczby jaką można otrzymać z takiego procesu.

10 --> 1^2 + 0^2= 1
11--> 1^2 + 1^2 = 2

Chodzi Ci o zamianę liczby na sumę kwadratów cyfr jej reprezentacji dziesiętnej? Jeśli tak to zamień na stringa i licz sumę kwadratów dla cyfr. Jeśli to jakieś spojowe zadanie to pomyśl też o jakiejś memoizacji.

Ja bym to robił tak, bo prosto:

1. Pociąć liczbę na cyfry, wrzucić w wektor.
2. std::transform na wektorze by zrobić podnoszenie wartości cyfr do kwatratu.
3. std::accumulate by zsumować.

Wydaje mi się, że będzie tutaj parę cykli. Przykładowo jeśli osiągniesz 2, to nie ma sensu iść dalej, bo potem wpadniesz w cykl 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4. Wyszło mi, że najmniejsze możliwe wartości do osiągnięcia (ogólnie) to tylko 1, 2, 3, 4. Wszystkie pozostałe liczby prędzej czy później wpadną w cykl prowadzący do jednej z tych wartości.

@Althorion:

Przenosząc dyskusję z komentarzy:

int sum_of_squared_digits_kq(int val)
{
    auto str = std::to_string(val);
    auto sum_with_char = [](int total, char c) { return total + pow(c-'0',2); };
    return std::accumulate(str.cbegin(), str.cend(), 0, sum_with_char);
}

int sum_of_squared_digits_althorion(int val)
{
    vector<int> digits(12, 0);
    int i = 0;
    auto sum = [](int total, int c) { return total + pow(c, 2); };
    while(val) { digits[i] = val % 10; ++i; val /= 10; }
    return std::accumulate(digits.cbegin(), digits.cend(), 0, sum);
}

Abstrahując od wydajności, wciąż preferuję wersję moją.

Nie jestem na 100% pewien czy to nie ma buga, ale wydaje się, że prosta rekurencja załatwia sprawę:

int sum_square_digits(int n) {
	 int s = 0;
	 while ( n != 0) {
		s += (n % 10) * (n % 10);
		n /= 10;
	 }
	 return s;
}

int sum_square_while(int n) {
	if (n / 10 == 0) return n;
	else
		return sum_square_while(sum_square_digits(n));
}

Jeśli to faktycznie zadanie ze spoja to przeważnie liczba na wejściu <= 10^9
Naiwne rozwiązania nie przejdą. Prawdopodobnie trzeba użyć memoizacji i rekurencji powyżej wartości liczby, przekraczającej granicę alokacji tablicy.