SWUST.OJ#274:函数求值

目录

题目

题目分析

代码演示

递归代码

循环代码

题目

题目分析

首先啊，我们来理解一下这个题目是什么意思呢？多组输入，每组会输入一个数n，对应会输出一个值并换行，那这个值是什么呢？也就是f(n)的值，而f(n)又是由什么组成的呢？它的值应该等于g(1)+....+g(n)，那函数g(n)的意思是什么呢？题目中定义函数g(n)为n的最大奇数因子。我们很容易就脑海里面出现了一个想法，如果n是奇数那么g(n)的值便等于n，如果n是偶数,那么就对n一直除以2，一直到剩下的数是奇数，假设这个数是m吧，那么g(n)就应该等于m，然后把g(1)到g(n)都进行这个操作，并把他们的返回值加起来，就是最后的结果，这个思路是没有问题的，但是这是典型的暴力行为。

我提出以下两点问题：

• 如果n取最大值10的8次方，我们不妨先把g(1)+g(3)+...+g(10^8-1)奇数项加起来，看看是多少，这是多少呢？1+3+5+...+10^8-1应该等于（10^16）/4（等差数列求和）肯定是超过了int的范围的，int的范围是-2^31~2^31-1，而long long的数据范围为-2^63~2^63-1，所以在定义储存结果数据的变量时，应该使用long long去定义，int与long long的参数如下：

所以我们应该知道，int数据范围的上界，应该是大于2*10^9次方的，而long long数据范围的上界，应该是大于9*10^18次方的，那是不是以后我们定义变量的时候都用long long呢？我的回答是："NO!"，定义一个long long类型的变量必然会占用更多的内存资源，作为一名优秀的程序员应该懂得合理的利用系统的内存资源，一味的图方便并不是长远之计，如果想彻底了解为什么int的数据范围是这样，long long的数据类型是那样，可以自己去了解，原码，反码，补码的内容，这里博主不做过多的阐述！

• 我们可以设想，如果n取很大的数，就比如取10的8次方，那我们就要去一个一个检测，总共次数绝对是大于10^8次方的，因为有些偶数，要检测多次，对于一个值为2^30次方的数，便要检测30次，再加上是多组测试数据，它的运行时间是肯定超过1ms的，这就是所谓的暴力解法，会报错TLE，那我们是否可以进行优化呢？答案是："YES！"，我们看下面的分析：

f(n) = 所有奇数项之和 + 所有的偶数项，除以2

所有的偶数项除以2 = 当前所有奇数项之和 + 当前所有的偶数项除以2

一直反复下去,直到n为1

举例：f(8) = 1 + 3 + 5 + 7 + g(2/2) + g(4/2) + g(6/2) + g(8/2)

           f(4) = g(1) + g(2) + g(3) + g(4) = 1 + 3 +g(2/2) + g(4/2)

           f(2) = g(1)+ g(2) = 1 +g(2/2)

           f(1) = g(1) = 1 

补充(等差数列求和)：

当n为奇数，公差为2时，sum = (1+n)*(1+n)/4

当n为偶数，公差为2时,   sum = n*n/4

代码演示

递归代码

#include
long long f(long long n)
{if(n==1) return 1;else if(n%2!=0) return (n+1)*(n+1)/4+f(n/2);else return n*n/4+f(n/2);
}
int main()
{long long n;while(scanf("%lld",&n)!=EOF){printf("%lld\n",f(n));}return 0;
}

循环代码

#include
int main()
{long long n;while(scanf("%lld",&n)!=EOF){long long sum=0;while(n!=0){if(n%2!=0) sum+=(n+1)*(n+1)/4;else sum+=n*n/4;n/=2;}printf("%lld\n",sum);}return 0;
}

此篇博客主要是面向编程初学者的，故全文采用的是纯C语言编写，有疑问欢迎大家评论区留言！！！