//问题说明
//用c写程序找出2～999之间的同构数，同构数是这样的。他出现在他的平方的右边如5的平方＝25，25的右端是5，所以5是一个同构数
//发现贴上来的原因是我发现这个程序的优化效果比较明显.
//从最初版到最终版的用时相差100多倍.
//我使用了多媒体时钟编译时需链接winmm.lib
//我的编译选项是:
//cl /O2 /MD /DWIN32 /D_WINDOWS winmm.lib tonggou.cpp
/////////////////////////////////////////////////////////////////////////////
//1.最直接的版本(看看我理解错了没有)
//那么从2开始到31为至的数m,依次求出它们的平方M.
//将m和M转化为字符串.长度分别是n,mn.
//从M的第mn-n位开始与m进行字符串的比较.如果相等,m就是同构数.
/////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <windows.h>
int check(int n)
{
char buf_n[12] = {0};
char buf_m[12] = {0};
itoa(n, buf_n, 10);
itoa(n * n, buf_m, 10);
int len_n = strlen(buf_n);
int len_m = strlen(buf_m);
if (len_m < len_n)
{
return false;
}
return 0 == strcmp(buf_n, &buf_m[len_m - len_n]);
}
int main()
{
DWORD begin = timeGetTime();
for (int i = 2; i < 100000 ; i++)
{
if (check(i))
{
printf("%d 是同构,它的平方是%d/n", i, i * i);
}
}
DWORD end = timeGetTime();
printf("共用时 %d ms", end - begin);
return 0;
}
////////////////////////////////////////////////////////////////////////////////
//2.优化版
////////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <windows.h>
int top(int n)
{
int top_n = 10;
while (n > top_n - 1)
{
top_n *= 10;
}
return top_n;
}
int check(int n)
{
return (n * n - n) % top(n) == 0;
}
int main()
{
DWORD begin = timeGetTime();
for (int i = 2; i < 100000 ; i++)
{
if (check(i))
{
printf("%d 是同构,它的平方是%d/n", i, i * i);
}
}
DWORD end = timeGetTime();
printf("共用时 %d ms", end - begin);
return 0;
}
////////////////////////////////////////////////////////////////////////////////
//3.最终版
//分析:
//n * n = x*100 + n
//n * n - n - x = 0;
//解得
// n = 1/2 + sqrt(4*x + 1)/2
// x = 10 * y或100*y 或1000*y (y 为自然数) 取值与 n的大小有关
// 只有1, 9结尾的数才有形为xxx1的平方数.
// k = sqrt(4 * x + 1) = 2 * n - 1 <= 999 * 2 - 1 = 1997
//
// 解决方案
// 在2~1997范围内,取1或9结尾的数, k
// 由 n = (k + 1) /2 求取n
// 由 x = (k * k - 1) /4 求取x
// 判断 n 和 x的关系是否满足要求: x % top(n) == 0
//
////////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <time.h>
#include <windows.h>
int top(int n)
{
int top_n = 10;
while (n > top_n - 1)
{
top_n *= 10;
}
return top_n;
}
int getn(int k)
{
return (k + 1) / 2;
}
int getx(int k)
{
int sqrt_4x = k* k - 1;
if (sqrt_4x & 0x3)
{
//不能整除4
return 0;
}
return sqrt_4x >> 2;
}
bool check(int k)
{
int n = getn(k);
int x = getx(k);
if (x > 0 && n > 1)
{
return x % top(n) == 0;
}
return false;
}
int max_k(int n)
{
return n * 2;
}
#define N 100000
int main()
{
DWORD begin = timeGetTime();
int array_k[100];
int count_k = 0;
for (int i = 11; i < max_k(100000) ; i += 10)
{
if (check(i))
{
array_k[count_k++] = i;
}
}
for (int i = 9; i < max_k(100000) ; i += 10)
{
if (check(i))
{
array_k[count_k++] = i;
}
}
for (int i = 0; i < count_k; i++)
{
int n = getn(array_k[i]);
printf("%d 是同构,它的平方是%d/n", n, n * n);
}
DWORD end = timeGetTime();
printf("共用时 %d ms", end - begin);
return 0;
}
/*
前两版都有溢出的bug,最终版没有.
执行结果(PIII 500MHz)
1.直观版
---------- Run Application ----------
5 是同构,它的平方是25
6 是同构,它的平方是36
25 是同构,它的平方是625
76 是同构,它的平方是5776
376 是同构,它的平方是141376
625 是同构,它的平方是390625
9376 是同构,它的平方是87909376
87231 是同构,它的平方是-980687231
共用时 183 ms
优化版
---------- Run Application ----------
5 是同构,它的平方是25
6 是同构,它的平方是36
25 是同构,它的平方是625
76 是同构,它的平方是5776
376 是同构,它的平方是141376
625 是同构,它的平方是390625
9376 是同构,它的平方是87909376
87232 是同构,它的平方是-980512768
共用时 9 ms
3.最终版
---------- Run Application ----------
6 是同构,它的平方是36
76 是同构,它的平方是5776
376 是同构,它的平方是141376
9376 是同构,它的平方是87909376
5 是同构,它的平方是25
25 是同构,它的平方是625
625 是同构,它的平方是390625
共用时 3 ms
其实想起来,做到优化版就可以了.必竟写程序也要时间,我在直观版用了10分钟,优化版用了5分种,而终版用了一个小时(主要是分析过程).
总体来说,做到最终版不合算.
*/