简单数学题.ppt
《简单数学题.ppt》由会员分享,可在线阅读,更多相关《简单数学题.ppt(29页珍藏版)》请在三一文库上搜索。
1、简单数学题,ACShiryu http:/ The 3n + 1 problem,题目大意: 给一个整数n,如果n是偶数,把它除以2;如果n是奇数,把它乘3加1.用新得到的值重复上述步骤,直到n=1时停止,例如对于n=22时有如下的生成序列 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 对于给定的n,该序列的元素(包括1)个数被称为n的循环节长度。在上述例子中,22的循环节长度是16.现在输入i和j,你的任务是计算i与j(包括i和j)之间的整数中,循环节长度的最大值,2019/7/21,3,Input: 两个整数i,j,0i,j10 000,poj120
2、7 The 3n + 1 problem,Output: 先按原来的顺序输出i和j,然后输出二者中最大的循环节长度,Sample Input 1 10 100 200 201 210 900 1000,Sample Output 1 10 20 100 200 125 201 210 89 900 1000 174,2019/7/21,4,分析题目难点:,1:判断整数的奇偶性 2:如何求n的循环节长度 3:如何求一段序列中的最大循环节长度,用n%2,如果等于1则为奇数,等于0,则为偶数,设置一个计数器,每对n操作一次就计数+1,直到n=1,则跳出循环,并将结果保存在数组里,设置一个临时变量,初
3、始为j的循环节长度,遍历从i到j的所有的数,如果遇到循环节大于临时变量的数,就将该循环节长度赋给临时变量,int count = 0,t=n; while(n!=1) count+; if(k%2) k=k*3+1; else k=k/2; numt=count;,int tmp = numj; for(k=i;kj;k+) if(tmpnumk) tmp=numk;,2019/7/21,5,完整程序:,int a, b ; while(scanf(“%d%d“, ,#include using namespace std; int num10005; int main() int i; me
4、mset(num,0,sizeof(num); for(i=2;i=10000;i+) int k=i; while(k!=1) numi+; if(k%2) k=k*3+1; else k=k/2; ,WrongAnswer,2019/7/21,6,为什么会这样?,让我们再仔细看下题目的输入输出,Input: 两个整数i,j,0i,j10 000,Output: 先按原来的顺序输出i和j, 然后输出二者大的循环节长度,原来有陷阱,题目并没有规定i必须小于j,对于ij的情形需要交换i和j的顺序再进行寻找。现在就可以AC了!,2019/7/21,7,更多的问题:,更改后的代码怎么写?,输入数据中
5、的i和j的要求改为0i,j1 000 000怎么办? 还能那样求吗?小心TLE! 详情见Uva的100题: http:/uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36,2019/7/21,8,poj2773 Happy 2006,题目大意就是给出n和k求出第k个与n互素的数(1 = n = 1000000), k (1 = k = 100000000).,Input: n ,k,Output: 第k个与n互素的数,Sample Input
6、2006 1 2006 2 2006 3,Sample Output 1 3 5,2019/7/21,9,分析题目难点,1:题目特点 2:如何判读两个数互素 3:如何快速求两个数的最大公约数,数据大,传统的循环到第k个数一定会超时,互素说明两个数的最大公约数为1,以前的从2循环到sqrt(n)肯定不行,会超时 这里要用到欧几里德算法:gcd(a,b)=gcd(b,a%b),int gcd(int a,int b) return b=0?a:gcd(b,a%b); 见算法入门竞赛经典第177页,2019/7/21,10,还能不能更快.,这样做依旧会超时,k的最大值是100000000,让我们先来
7、观察几组数剧后再来讨论,2019/7/21,11,仔细看,有什么发现?,对比一下下面的表格:,(n)是欧拉函数,表示对于正整数n,与n互素且不大于n的正整数的个数,2019/7/21,12,原来是这样.,原来第k个与n互素的数对k的模具有周期性,周期正好就是(n) (n)是欧拉函数,表示对于正整数n,与n互素且不大于n的正整数的个数,2019/7/21,13,gcd(bt+a,b)=gcd(a,b)(t为任意整数),所以a与b互素等价于bt+a与b互素,故与m互素的数对m取模具有周期性,,假设小于m的数且与m互素的数有k个,其中第i个是ai,则第mk+i与m互素的数是km+ai,证明过程:,2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 简单 数学题
链接地址:https://www.31doc.com/p-3176595.html