01-简单计算题1.ppt

计算: 1-2+3-4+5-6+7......+n long fn(long n) { long sum=0; int i, flag=1; for (i=1; i=n; i++) { sum = sum+flag*i; flag = -flag; } return sum; } long fn(long n) { long sum=0; int j=1, i=1, flag=1; while (j=n) { sum = sum+i; i = -i; i0 ? i++ : i--; j++; } return sum; } long fn(long n) { if(n%2==0) return (n/2)*(-1); else return (n/2)*(-1)+n; } 最大公约数问题 写一个程序，求两个正整数的最大公约数。如果两个正整数都很大，有什么简单的算法吗？ 解法一：辗转相除法 示例如下： f (42, 30) = f (30, 12) = f (12, 6) = f (6, 0) = 6 具体代码如下： int gcd(int x, int y) { return (!y) ? x : gcd(y, x%y) ; } 最大公约数问题 解法二：除法转换成减法 如果一个数能够同时整除 x 和 y，则必能同时整除 x-y 和 y。 能同时整除 x-y 和 y的数，也能够同时整除 x 和 y。 示例如下： f (42,30) = f (30,12) = f(12,18) = f(18,12) = f (12,6) = f(6,6) = f(6,0) = 6 具体代码如下： int gcd(int x , int y) { if (xy) return gcd(y, x); if (y==0) return x; else return gcd(x-y, y); } 最大公约数问题 解法三 如果：x = k*x1, y=k*y1，那么 f (x, y) = k * f (x1, y1) 如果：x = p*x1, y% p !=0，其中 p 为素数，那么 f (x, y) = f (x1, y) 取 p=2 若 x, y 均为偶数，f (x, y) = 2*f (x/2, y/2) = 2*f (x1, y1) 若 x 为偶数，y 为奇数， f (x, y) = f (x/2, y) = f (x1, y) 若 x 为奇数，y 为偶数， f (x, y) = f (x, y/2) = f (x, y 1) 若 x, y 均为奇数， f (x, y) =f (x, x - y) ，则 x-y为偶数，下一步必有除2的操作。 最大公约数问题 解法三：除法转换成减法 int gcd(int x , int y) { if(xy) return gcd(y,x); if(y==0) return x; else { if (IsEven(x)) { if (IsEven(y)) return (gcd(x1,y1)1); else return gcd(x1, y); } else { if (IsEven(y)) return gcd(x, y1); else return gcd(y, x-y); } } } 分牛问题 传说古印度有一位老人，临终前留下遗嘱，要把19头牛分给3个儿子。老大分总数的1/2，老二分总数的1/4，老三分总数的1/5。 按照印度的教规，牛被视为神灵，不能宰杀，只能整头分。然而，先人的遗嘱更需无条件遵守。老人去世后，3兄弟为分牛一事绞尽脑汁，无计可施，最后决定诉至官府。 请问，你如何处理此事？ 传说古印度有一位老人，临终前留下遗嘱，要把 n头牛分给 3 个儿子。老大分总数的1/i，老二分总数的1/j，老三分总数的1/k。 朴秀峰 xfpiao@126.com 问题求解与程序设计 程序举例 鸡兔同笼 棋盘上的距离 校门外的树 填词 装箱问题 贷款利率 计算: 1-2+3-4+5-6+7+...+n 确定进制 skew数 鸡兔同笼 问题描述 一个笼子里面关了鸡和兔子(鸡有2 只脚，兔子有4 只脚，没有例外)。已经知道了笼子里面脚的总数 a，问笼子里面至少有多少只动物，至多有多少只动物? 输入数据 第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a (a 327