语言 水仙花数算法-水仙花数代码如何减短运行时间

问题描述

水仙花数代码如何减短运行时间

水仙花数是指一个N位正整数(N>=3),它的每个位上的数字的N次幂之和等于它本身。例 如:153 = 13 + 53+ 33。 本题要求编写程序,计算所有N位水仙花数。

输入格式:

输入在一行中给出一个正整数N(3<=N<=7)。

输出格式:

按递增顺序输出所有N位水仙花数,每个数字占一行。
输入样例:3

输出样例:153
370
371
407

我的代码运行起来超时;我知道可能是n=7时循环次数太多造成的.有什么办法解决呢

include

include

int main()
{
int n,i,x;
scanf("%d", &n);
x=pow(10,n-1);
int y=pow(10,n);
int sum,a,z,flag;
for(i=x;i
{
z=x;
sum=0;
flag=i;
while(z>0)
{
a=flag/z;
sum+=pow(a,n);
flag=flag%z;
z/=10;
}
if(sum==i) printf("%dn", i);
}
return 0;
}

解决方案

pow的效率很低,因为它是浮点运算,可以直接内联整数循环,甚至可以数组查表来代替。这样可以快很多。

解决方案二:

int pow10[] = { 1, 10, 100, 1000, 10000, ... };

int y=pow(10,n);
->
int y=pow10[n];

解决方案三:

感谢楼上的提醒,我自己写了个power函数就通过了

#include <stdio.h>

int mypow(int a, int ae) //不要用math的pow函数,因为是浮点运算,太慢了
{
    int powret;
    if (a == 0 || a == 1) //对于0和1的情况,没有必要计算
        powret = a;
    else {
        powret = 1;
        while (ae > 0)
        {
            powret = powret * a;
            ae--;
        }
    }

    return powret;
}

int split_and_sum(int i, int e) {
    int ret = 0;
    while (i > 0) {
        ret += mypow(i % 10, e);
        i /= 10;
    }

    return ret;
}

int main(void)
{
    int N;
    scanf("%d", &N);
    int min = 10, max;

    min = mypow(min, N - 1);//注意,3位数只有2个0
    max = min * 10;

    for (int i = min; i < max; ++i)
    {
        int sum = split_and_sum(i, N);
        if (sum == i)
            printf("%dn", i);
    }

    return 0;
}

时间: 2016-02-04

语言 水仙花数算法-水仙花数代码如何减短运行时间的相关文章

C语言二分查找算法及实现代码_C 语言

二分査找也称折半査找,其优点是查找速度快,缺点是要求所要査找的数据必须是有序序列.该算法的基本思想是将所要査找的序列的中间位置的数据与所要査找的元素进行比较,如果相等,则表示査找成功,否则将以该位置为基准将所要査找的序列分为左右两部分.接下来根据所要査找序列的升降序规律及中间元素与所查找元素的大小关系,来选择所要査找元素可能存在的那部分序列,对其采用同样的方法进行査找,直至能够确定所要查找的元素是否存在,具体的使用方法可通过下面的代码具体了解. #include <stdio.h> binar

C语言选择排序算法及实例代码_C 语言

选择排序是排序算法的一种,这里以从小到大排序为例进行讲解. 基本思想及举例说明 选择排序(从小到大)的基本思想是,首先,选出最小的数,放在第一个位置:然后,选出第二小的数,放在第二个位置:以此类推,直到所有的数从小到大排序. 在实现上,我们通常是先确定第i小的数所在的位置,然后,将其与第i个数进行交换. 下面,以对 3  2  4  1 进行选择排序说明排序过程,使用min_index 记录当前最小的数所在的位置. 第1轮 排序过程 (寻找第1小的数所在的位置) 3  2  4  1(最初, m

C语言写的求水仙数

C语言写的求水仙数,判断并输出水仙数的部分是在函数里面实现,代码如下:: //本人英文水平不是很好所以就拿中文做注释#include "stdio.h"void is(int a,int b)...{    //定义三个变量作为    int i,j,k;    for(;a<=b;a++)    ...{        i=a%10;//所求数的个位        j=(a/10)%10;//所求数的十位        k=a/100;//所求数的百位        if(i*

C++实现顺序排序算法简单示例代码_C 语言

本文实例讲述了最直接的顺序排序法VC++示例代码,还记得以前上学时候这是计算机的必考题,而且在排序算法中,顺序排序似乎是最简单的了,也是最容易掌握的.现在列出来让大家重新回顾一下! 具体代码如下: //顺序排序 void InsertSort(int r[], int n){ for (int i=2; i<n; i++){ r[0]=r[i]; //设置哨兵 for (int j=i-1; r[0]<r[j]; j--) //寻找插入位置 r[j+1]=r[j]; //记录后移 r[j+1]

C语言 奇偶排序算法详解及实例代码_C 语言

C语言奇偶排序算法 奇偶排序,或奇偶换位排序,或砖排序,是一种相对简单的排序算法,最初发明用于有本地互连的并行计算.这是与冒泡排序特点类似的一种比较排序.该算法中,通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换.下一步重复该操作,但针对所有的(偶-奇)位置数字对.如此交替进行下去. 使用奇偶排序法对一列随机数字进行排序的过程 处理器数组的排序 在并行计算排序中,每个处理器对应处理一个值,并仅有与左右邻居的本地互连.所有处理器可同时与邻居进行比较.交

C语言解决螺旋矩阵算法问题的代码示例_C 语言

赶集网校招就采用了螺旋输出矩阵作为程序题,要求将矩阵螺旋输出如: 图中6*6矩阵线条所示为输出顺序,如果输出正确的话应该输出1~36有序数字.  我想的是这么做的: #include <stdio.h> //#define LEN 1 //#define LEN 2 //#define LEN 3 #define LEN 4 void printClock(int a[][LEN]){//输出函数 int t; int i = 0, m = 0; int j = LEN, n = LEN; w

c语言的高精度算法提问

问题描述 c语言的高精度算法提问 谁能简单说一下高精度算法是怎么意思!谁能简单说一下高精度算法是怎么意思!谁能简单说一下高精度算法是怎么意思!谁能简单说一下高精度算法是怎么意思! 解决方案 C语言 高精度算法 解决方案二: 要高精度的算法可以嵌套汇编对于时间控制或是对于单片机开发常用的 解决方案三: 解决方案四: 高精度算法通常是指大整数的加减乘除取模以及乘方运算.主要的思想就是将一个大数储存在数组内(每一个元素一位). 例如8382可以表示为 int a[] = {2,8,3,8} (倒存为了

C语言数据结构:表达式求值代码问题

问题描述 C语言数据结构:表达式求值代码问题 要求允许小数,过滤空格,可以+ - * /和求指数 #include #include #include #include #define true 1 #define false 0 #define OPSETSIZE 8 //运算符集合数为8 char OPSET[OPSETSIZE] = { '+', '-', '*', '/', '(', ')', '#', '^' }; unsigned char Prior[8][8] = { /****

游戏编程-求有详细注释的matlab 智能算法相关的代码

问题描述 求有详细注释的matlab 智能算法相关的代码 网盘,邮箱[email protected] 无聊者勿扰![ 解决方案 ? <神经网络入门> .? (连载之一) 用平常语言介绍神经网络(Neural Networks in Plain English) 因为我们没有很好了解大脑,我们经常试图用最新的技术作为一种模型来解释它.在我童年的时候,我们都坚信大脑是一部电话交换......<br/><strong>答案就在这里:</strong><a t