Преобразование рекурсивного алгоритма в линейный

f(n,m)=

    m=1: n

    n<m*m: f(n,m-1)

    иначе: min(f(n,m-1),f(n-m*m,m)+1)

Найти f(N,(int)sqrt(N)).

for(i = 0; i <= n; i++){a=i;}


    for(m = 2; m*m <= n; m++)

    {

    	for(i = m*m; i <= n; i++){

    		a = min(a + 1, a);

    	}

    }

В магазине продаются квадратные плитки различных цветов. Пете нужно купить N плиток и сложить из них мозаику, в которой плитки одного цвета образуют квадрат и ни в какой другой квадрат не входят. Таким образом, из N плиток должно получиться какое-то количество квадратов различных цветов. Например, из 10 плиток можно сложить два квадрата со сторонами 3 и 1, или четыре квадрата  со сторонами 2, 2, 1, 1. Петя задумался — какое минимальное количество цветов при этом можно использовать. Помогите ему это определить.


Входные данные: Во входном файле записано одно число N (1 ≤ N ≤ 30000).

Выходные данные: Выходной файл должен содержать единственное целое число — минимальное количество различных цветов.


Примеры:

input.txt     output.txt

10              2

3                3

18              2

Похоже на лаб.работу ..

#include <iostream>

using namespace std;

int ans;

int main()

{

	int n, i, j, t;

	cin>>n;

	ans = 0;

	for(i=1; i<=n; i++)

	{

		ans = i;

		for(j=1; j*j<=i; j++)

		{

			t = ans+1;

			if(t < ans) ans = t;

		}

	}

	cout<<ans<<endl;

	return 0;

}

int f(int n)

{

	int i, m;

	int a;


    for(i = 0; i <= n; ++i){ a=i; }


    for(m = 2; m * m <= n; ++m){

        for(i = m * m; i <= n; ++i){

        	a = min(a + 1, a);

        }

    }

    return a;


}