首页 > 代码库 > Street Numbers
Street Numbers
Description
Write a program to find pairs of numbers that satisfy this condition. To start your list the first two pairs are: (house number, last number):
6 8
35 49
Input
Output
Sample Output
6 8 35 49
方法一:
题意:有1~m间屋子,并按1到m排列,有一人a住在第n间屋子。现要输出从1加到n-1和从n+1加到m的和相同时的n和m。
思路:考察佩尔方程 由题意得
1+2+……+n-1=n*(n+1)/2
(n+1)+(n+2)+……+m=(m-n)*(m+n+1)/2 即n*(n+1)=(m-n)*(m+n+1)
化简得:2*n^2=m^2+m --> 8*n^2=(2*m+1)^2 -1 --> (2*m+1)^2 -8*n^2=1
令x=2*m+1,y=n,d=8
事先可以知道其中的最小解:x=3,y=1 接下来就是迭代了。
佩尔方程原型:X^n - D*Y^n = 1
其中佩尔方程的迭代公式:Xn = Xn-1 * X1 + d * Yn-1 * Y1
Yn = Xn-1 * Y1 + Yn-1 * X1
代码:
#include<stdio.h>int main(){ int x,y,count=10; int x1=3,y1=1,prex=3,prey=1,d=8; while(count--) { x=prex*x1+d*prey*y1; y=prex*y1+prey*x1; printf("%10d%10d\n",y,(x-1)/2); prex=x; prey=y; } return 0;}
方法二:
题目实际就是给你两个数m、n,使得m、n之间的数之和与1~m之间的数之和相等(不包括m)。
即:1+2+...+m-1 == (m+1)+...+n; 因此我们可以套用求和公式,两边移项化简得:2*pow(m,2) = n*(n+1)。
因此我们可以得到:m = sqrt(n*(n+1)/2)。枚举n的值,从而判断所得到的m值是否为整数,若为整数则说明两边的值实际相等。得到输出满足条件的最小的十组m、n,注意格式“%10d”,打表输出。
代码如下:
求满足条件的m,n:
代码:
#include<stdio.h>#include<math.h>int main(){ long long _mid; double mid; for(int i=6; i<100000000; i++) { mid = (double)i*(i+1); mid /= 2; mid = sqrt(mid); _mid = mid;// 取mid的整数部分 if(fabs(mid-(double)_mid) < 1e-10)//若整数部分与本身相等则说明符合条件 printf("%10I64d%10d\n", _mid, i); } return 0;}
方法3:打表法
代码:
#include <stdio.h>int main(){ printf("%10d%10d\n", 6, 8); printf("%10d%10d\n", 35, 49); printf("%10d%10d\n", 204, 288); printf("%10d%10d\n", 1189, 1681); printf("%10d%10d\n", 6930, 9800); printf("%10d%10d\n", 40391, 57121); printf("%10d%10d\n", 235416, 332928); printf("%10d%10d\n", 1372105, 1940449); printf("%10d%10d\n", 7997214, 11309768); printf("%10d%10d\n", 46611179, 65918161); return 0;}
另一代码:
#include<stdio.h>int main(){ int c=0,t=1,i,j,temp; int x[15]={3},y[15]={2}; while(c<10) { x[t]=x[t-1]*x[0]+2*y[t-1]*y[0]; y[t]=x[t-1]*y[0]+y[t-1]*x[0]; t++; c++; } for(i=1;i<11;i++) printf("%10d%10d\n",y[i]/2,(x[i]-1)/2); //system("pause"); return 0;}