优化同构数查找程序的方法

//问题说明
//用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分种,而终版用了一个小时(主要是分析过程).
总体来说,做到最终版不合算.
*/