洛谷P1028 数的计算 (C语言 + 详细注释 + 两种方法实现)

 

//首先，自我认为题意有点模糊不清（qwq），第二个条件的原数指什么？我以为是输入的那个数，但是这样的话当输入6时不就有无数个解了吗？百思不得其解，所以这道题我就搁置了很久，后来看到大佬们的题解才知道这个“原数”指新加的那个数，那么就解释的通了，比如输入6时，2 < 6 / 2 = 3, 得到了26，新数是2，不超过2 / 2 = 1的自然数只能取1（虽然0也是自然数，但是十进制数不能以0开头，故不考虑啦！），所以又形成了126，又1 / 2 = 0，找不到比0小的自然数了，所以这种情况完了。看完上述这个例子，可以很容易发现可以递归做，于是我就写了一种递归的写法，结果发现一片TLE（time limit exceeded),qwq。因为最大数据达到了1000，递归的话很耗时间，超时也在情理之中。无可奈何，只能另寻他法，那就找规律咯，我就写了几项，有点懒，就用图片代替（哈哈哈！！)，可以看出n为奇数时，a[n] = a[n - 1],; n为偶数时，a[n] = a[n - 1] + a[n / 2]。下面证明这俩式子的正确性。n为奇数时，n / 2 ==（n - 1）/ 2，所以结果一样。n为偶数时，1 ~ （n / 2）比1 ~ （ (n - 1）/ 2)多了个 n / 2，由上述的递归知道前者就比后者多了个a[n / 2]；

下面是我的两种代码及运行结果

法一：递归
#include<stdio.h>
int fun(int n);
int main() {
	int n;
	scanf("%d", &n);
	for(int i = 0; i <= 10; i++)
		printf(" a[%d] = %d\n", i, fun(i) + 1);

	return 0;
}

int fun(int n) {
	int i, cnt;
	cnt = 0;
	for (i = 1; i <= n / 2; i++) {
		cnt += fun(i);
		cnt++;
	}
	return cnt;
}

结果：（只有5个绿，qwq）

法二:递推公式
#include<stdio.h>
int main() {
	int i, n, a[1005] = {1, 1};  //a[0]和a[1]初始化为1
	scanf("%d", &n);
	for (i = 2; i <= n; i++)
		if (i & 1)           //i & 1不为0说明i是奇数，因为1的位模式最后一位是1，如果i是奇数，最后一位也是1，与操作结果为1，否则结果为0
			a[i] = a[i - 1];
		else
			a[i] = a[i - 1] + a[i / 2];
	printf("%d\n", a[n]);

	return 0;
}

结果：（有时候一片绿也很好啊，嘻嘻嘻！！)