C语言程序实践(入门之二)

《C语言程序实践(入门之二)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、丽水学院计算机与信息工程学院C语言程序实践教学组第四章ACM入门（之二）内容提要数学题规律题简单字符串题贪心算法递推求解一、数学题的解题思路1．数学题主要是把问题理解清楚，特别是其中的数学关系。2．特别大的数字主要看题目的内容会不会溢出。如果溢出可以用LONG32位，不行再加个LONG64位。在VC下不支持，在GC++中支持。3．用浮点数也要考虑精度和输出的位数。一、数学题的解题思路例题：鸡兔同笼问题描述一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物？输入数据第1行是测试数据的组

2、数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(a<32768)。输出要求n行，每行输出对应一个输入。输出是两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用空格分开。如果没有满足要求的情况出现，则输出2个0。一、数学题的解题思路输入样例2320输出样例00510一、数学题的解题思路解题思路这个问题可以描述成任给一个整数N，如果N是奇数，输出00，否则，如果N是4的倍数，输出N/4N/2，如果N不是4的倍数，输出N/4+1N/2。这是一个一般的计算题，只要实现相应的判断和输入、输出代码就可以了。题目中说明了输入整数在一个比较小的范围内，所

3、以只需要考虑整数运算就可以了。一、数学题的解题思路参考程序#includevoidmain(){intnCases,i,nFeet;//nCases表示输入测试数据的组数，nFeet表示输入的脚数。scanf("%d",&nCases);for(i=0;i

4、有2只脚printf("%d%d",nFeet/4+1,nFeet/2);elseprintf("%d%d",nFeet/4,nFeet/2);}}二、规律题的解题思路1．确定系统中的规律。2．可以通过查看输出结果的方式查找规律，有些题目可能要好几个数据后有规律。3．一般1S的题目，而且看起来可以用循环解决的要考虑规律。4．一般1S可以循环1000万次左右。二、规律题的解题思路例题：数字序列问题描述一个数字序列由以下公式定义f(0)=7,f(1)=11,f(n)=f(n-1)+f(n-2)输入数据测试用例由多行构成，每行有1个数字n(2<=n<=1,000,00

5、0)输出要求每个测试用例输出一行，如果f(n)能被3整除则输出“YES”，否则输出“NO”二、规律题的解题思路输入样例234输出样例YESNONO二、规律题的解题思路解题思路本题如果直接用递归做肯定超时，只能去发现题目的规律。先用递归程序求出n=2..20时值，值如下所示：f(2)=18,f(3)=29,f(4)=47,f(5)=76，f(6)=123，f(7)=199，f(8)=322，f(9)=521，……除以3后的余数分别是：0221011202210112022从上面的数字可以发现规律n=2，6，10，14，18能被3整除。知道规律后程序就非常简单了。二、规律题

6、的解题思路参考程序#includevoidmain(){intn;while(scanf("%d”,&n)!=EOF)//测试用例由多行构成{if(n%4==2)//n=2，6，10，14，18……能被3整除printf(“YES”);elseprintf(“NO”);}}