找自幂数的逐步优化算法
自幂数是指一个 n 位数，它的每个位上的数字的 n 次幂之和等于它本身。（例如：当n为3时，有1^3 + 5^3 + 3^3 = 153，153即是n为3时的一个自幂数）
自幂数包括：独身数、水仙花数、四叶玫瑰数、五角星数、六合数、北斗七星数、八仙数、九九重阳数、十全十美数 。
下面分析怎样找出自幂数的算法：
1：首先要能判断一个自幂数
(这里面可以分为几个函数
1.找出数字的位数
2.给一个算次方的函数)
2：给定范围，查找自幂数
说到这里有的小朋友可能特别疑惑了，为神魔要自造一个算次方的函数呢?
C语言的math.h库里面不是有pow（）函数直接调用吗？
请注意本文章的标题，我们要优化，优化，优化，我们要给一个更快的方法，嘿哈。
先给出我第一次写出来的代码
#include <stdio.h>
#include <time.h>
#include "./include/mec.h"
boolean isSelfPower(int num);
int intLen(int num);
int intPow(int a, int p);
boolean isSelfPower(int num) {
int cnt;
int sum;
int n;
cnt = intLen(num);
sum = 0;
for (n = num; n && sum <= num; n /= 10) {
sum += intPow(n % 10 ,cnt);
}
return sum == num;
}
int main() {
int num;
int maxNum;
long startTime;
long endTime;
long deltaTime;
printf("输入最大范围:");
scanf("%d", &maxNum);
startTime = clock();
for (num = 0; num < maxNum; num++) {
if (isSelfPower(num)) {
printf("%d是自幂数\n", num);
}
}
endTime = clock();
deltaTime = endTime - startTime;
printf("耗时:%ld.%03lds\n", deltaTime / CLOCKS_PER_SEC, deltaTime % CLOCKS_PER_SEC);
return 0;
}
int intLen(int num) {
int cnt = 0;
if (num <= 0) {
return 1;
}
while (num) {
cnt++;
num /= 10;
}
return cnt;
}
int intPow(int a, int p) {
int sum = 1;
int i;
for (i = 0; i < p; i++) {
sum *= a;
}
return sum;
}
程序运行到这里，已经卡住了，头疼，头疼，这种算法可能
我们分析一下，计算长度能不能不用循环呢，我们这样想，可以定一个a[10]数组，a[0]为0，a[1]为10，a[2]为100，若最大范围数组小于a[i-1]大于a[i]则位数为i，这样不用循环，节省了时间，就很简单的判断了数字的位数！
我们再来看一下我们的，程序优化后的速度;
可是他还不够快，我还想更快！！！！！
我们直接给出一个二维数组，将数字的1到10次方的数值存到一个数组里面。
这样直接在数组里面找，不用再来循环叠加，再乘计算！
这样我们来看看最终的运行耗时！
我们在最后来给出最后完全的代码！
#include <stdio.h>
#include <time.h>
#include "./include/mec.h"
const int powValue[][10] = {
0, 1, 1, 1, 1, 1, 1, 1, 1, 1,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
0, 1, 2*2, 3*3, 4*4, 5*5, 6*6, 7*7, 8*8, 9*9,
0, 1, 2*2*2, 3*3*3, 4*4*4, 5*5*5, 6*6*6, 7*7*7, 8*8*8, 9*9*9,
0, 1, 2*2*2*2, 3*3*3*3, 4*4*4*4, 5*5*5*5, 6*6*6*6, 7*7*7*7, 8*8*8*8, 9*9*9*9,
0, 1, 2*2*2*2*2, 3*3*3*3*3, 4*4*4*4*4, 5*5*5*5*5, 6*6*6*6*6, 7*7*7*7*7, 8*8*8*8*8, 9*9*9*9*9,
0, 1, 2*2*2*2*2*2, 3*3*3*3*3*3, 4*4*4*4*4*4, 5*5*5*5*5*5, 6*6*6*6*6*6, 7*7*7*7*7*7, 8*8*8*8*8*8, 9*9*9*9*9*9,
0, 1, 2*2*2*2*2*2*2, 3*3*3*3*3*3*3, 4*4*4*4*4*4*4, 5*5*5*5*5*5*5, 6*6*6*6*6*6*6, 7*7*7*7*7*7*7, 8*8*8*8*8*8*8, 9*9*9*9*9*9*9,
0, 1, 2*2*2*2*2*2*2*2, 3*3*3*3*3*3*3*3, 4*4*4*4*4*4*4*4, 5*5*5*5*5*5*5*5, 6*6*6*6*6*6*6*6, 7*7*7*7*7*7*7*7, 8*8*8*8*8*8*8*8, 9*9*9*9*9*9*9*9,
0, 1, 2*2*2*2*2*2*2*2*2, 3*3*3*3*3*3*3*3*3, 4*4*4*4*4*4*4*4*4, 5*5*5*5*5*5*5*5*5, 6*6*6*6*6*6*6*6*6, 7*7*7*7*7*7*7*7*7, 8*8*8*8*8*8*8*8*8, 9*9*9*9*9*9*9*9*9,
};
boolean isSelfPower(int num);
int intLen(int num);
int intPow(int a, int p);
int intPow(int a, int p) {
return powValue[p][a];
}
int intLen(int num) {
if (num < 0) {
return 0;
}
if (num >= 100000000 && num < 1000000000) {
return 9;
}
if (num >= 10000000 && num < 100000000) {
return 8;
}
if (num >= 1000000 && num < 10000000) {
return 7;
}
if (num >= 100000 && num < 1000000) {
return 6;
}
if (num >= 10000 && num < 100000) {
return 5;
}
if (num >= 1000 && num < 10000) {
return 4;
}
if (num >= 100 && num < 1000) {
return 3;
}
if (num >= 10 && num < 100) {
return 2;
}
return 1;
}
boolean isSelfPower(int num) {
int cnt;
int sum;
int n;
cnt = intLen(num);
sum = 0;
for (n = num; n && sum <= num; n /= 10) {
sum += intPow(n % 10 ,cnt);
}
return sum == num;
}
int main() {
int num;
int maxNum;
long startTime;
long endTime;
long deltaTime;
printf("输入最大范围:");
scanf("%d", &maxNum);
startTime = clock();
for (num = 0; num < maxNum; num++) {
if (isSelfPower(num)) {
printf("%d是自幂数\n", num);
}
}
endTime = clock();
deltaTime = endTime - startTime;
printf("耗时:%ld.%03lds\n", deltaTime / CLOCKS_PER_SEC, deltaTime % CLOCKS_PER_SEC);
return 0;
}
/*int intLen(int num) {
int cnt = 0;
if (num <= 0) {
return 1;
}
while (num) {
cnt++;
num /= 10;
}
return cnt;
}
*/
/*
int intPow(int a, int p) {
int sum = 1;
int i;
for (i = 0; i < p; i++) {
sum *= a;
}
return sum;
}
*/
嘿嘿，这样就结束啦，如果你们能给出一个更加快速，时间复杂度更低的算法呢，欢迎留言，讨论，互相关注
后面还会提一些比较有意思的算法哦！！！
奇瑞汽车工作强度 23人发布