欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

7-4 水仙花数

程序员文章站 2022-06-07 14:39:17
...

7-4 水仙花数

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

输入格式:
输入在一行中给出一个正整数N(3≤N≤7)。

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

输入样例:

3

输出样例:

153
370
371
407

相信许多小伙伴第一眼看到这道题目就想到用循环嵌套了,然后调用一个C语言的次方函数pow(),代码如下:

#define _CRT_SECURE_NO_DEPRECATE 0
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(){
	int n, m;
	scanf("%d", &n);
		for (int x = 0; x<=9; x++){
			for (int y = 0; y <= 9; y++){
				for (int z = 0; z <= 9; z++){
					for (int j = 0; j <= 9; j++){
						for (int i = 0; i <= 9; i++){
							for (int k = 0; k <= 9; k++){
								for (int h = 0; h <= 9; h++){
										if (n == 3 && i * 100 + k * 10 + h == pow((double)i, (double)n) + pow((double)k, (double)n) + pow((double)h, (double)n)){
											if ((i * 100 + k * 10 + h)>=100)
												printf("%d\n", i * 100 + k * 10 + h);
										}
										else if (n == 4 && j * 1000 + i * 100 + k * 10 + h == pow((double)j, (double)n) + pow((double)i, (double)n) + pow((double)k, (double)n) + pow((double)h, (double)n)){
											if ((j * 1000 + i * 100 + k * 10 + h)>=1000)
												printf("%d\n", j * 1000 + i * 100 + k * 10 + h);
										}
										else if (n == 5 && z * 10000 + j * 1000 + i * 100 + k * 10 + h == pow((double)z, (double)n) + pow((double)j, (double)n) + pow((double)i, (double)n) + pow((double)k, (double)n) + pow((double)h, (double)n)){
											if ((z * 10000 + j * 1000 + i * 100 + k * 10 + h)>=10000)
												printf("%d\n", z * 10000 + j * 1000 + i * 100 + k * 10 + h);
										}
										else if (n == 6 && y * 100000 + z * 10000 + j * 1000 + i * 100 + k * 10 + h == pow((double)y, (double)n) + pow((double)z, (double)n) + pow((double)j, (double)n) + pow((double)i, (double)n) + pow((double)k, (double)n) + pow((double)h, (double)n)){
											if ((y * 100000 + z * 10000 + j * 1000 + i * 100 + k * 10 + h)>=100000)
												printf("%d\n", y * 100000 + z * 10000 + j * 1000 + i * 100 + k * 10 + h);
										}
										else if (n == 7 && x * 1000000 + y * 100000 + z * 10000 + j * 1000 + i * 100 + k * 10 + h == pow((double)x, (double)n) + pow((double)y, (double)n) + pow((double)z, (double)n) + pow((double)j, (double)n) + pow((double)i, (double)n) + pow((double)k, (double)n) + pow((double)h, (double)n)){
											if ((x * 1000000 + y * 100000 + z * 10000 + j * 1000 + i * 100 + k * 10 + h)>=1000000)
												printf("%d\n", x * 1000000 + y * 100000 + z * 10000 + j * 1000 + i * 100 + k * 10 + h);
										}
								}
							}
						}
						if (n == 3){
							scanf("%d", &m);
							exit(0);
						}
					}
					if (n == 4){
						scanf("%d", &m);
						exit(0);
					}
				}
				if (n == 5){
					scanf("%d", &m);
					exit(0);
				}
			}
			if (n == 6){
				scanf("%d", &m);
				exit(0);
			}
		}
	system("pause");
	return 0;
}

结果就是,代码运行超时了…
7-4 水仙花数
然后,我又换了个思路,优化了一下代码,用一重循环来做,代码如下:

#define _CRT_SECURE_NO_DEPRECATE 0
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(){
	int n, i = 0, j = 1;
	scanf("%d", &n);
	if (n == 3){
		i = 100;
		j = 999;
	}
	if (n == 4){
		i = 1000;
		j = 9999;
	}
	if (n == 5){
		i = 10000;
		j = 99999;
	}
	if (n == 6){
		i = 100000;
		j = 999999;
	}
	if (n == 7){
		i = 1000000;
		j = 9999999;
	}
	for (; i <= j; i++){
		if (n == 3 && i == pow((double)((i / 100) % 10),(double)(n)) + pow((double)((i / 10) % 10),(double)(n)) + pow((double)(i % 10),(double)(n))){
			printf("%d\n", i);
		}
		if (n == 4 && i == pow((double)((i / 1000) % 10),(double)(n)) + pow((double)((i / 100) % 10),(double)(n)) + pow((double)((i / 10) % 10),(double)(n)) + pow((double)(i % 10),(double)(n))){
			printf("%d\n", i);
		}
		if (n == 5 && i == pow((double)((i / 10000) % 10), (double)(n)) + pow((double)((i / 1000) % 10), (double)(n)) + pow((double)((i / 100) % 10), (double)(n)) + pow((double)((i / 10) % 10), (double)(n)) + pow((double)(i % 10), (double)(n))){
			printf("%d\n", i);
		}
		if (n == 6 && i == pow((double)((i / 100000) % 10), (double)(n)) + pow((double)((i / 10000) % 10), (double)(n)) + pow((double)((i / 1000) % 10), (double)(n)) + pow((double)((i / 100) % 10), (double)(n)) + pow((double)((i / 10) % 10), (double)(n)) + pow((double)(i % 10), (double)(n))){
			printf("%d\n", i);
		}
		if (n == 7 && i == pow((double)((i / 1000000) % 10), (double)(n)) + pow((double)((i / 100000) % 10), (double)(n)) + pow((double)((i / 10000) % 10), (double)(n)) + pow((double)((i / 1000) % 10), (double)(n)) + pow((double)((i / 100) % 10), (double)(n)) + pow((double)((i / 10) % 10), (double)(n)) + pow((double)(i % 10), (double)(n))){
			printf("%d\n", i);
		}
	}
	system("pause");
	return 0;
}

结果…还是超时7-4 水仙花数
我一琢磨,这应该问题出在pow()这个次方函数上面,于是上网一查,发现这个函数的时间复杂度比我们直接用乘号更大,所以…我直接舍弃了pow()函数,直接用乘号计算次方。

#define _CRT_SECURE_NO_DEPRECATE 0
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(){
	int n, i = 0, j = 1;
	scanf("%d", &n);
	if (n == 3){
		i = 100;
		j = 999;
	}
	if (n == 4){
		i = 1000;
		j = 9999;
	}
	if (n == 5){
		i = 10000;
		j = 99999;
	}
	if (n == 6){
		i = 100000;
		j = 999999;
	}
	if (n == 7){
		i = 1000000;
		j = 9999999;
	}
	for (; i <= j; i++){
		if (n == 3 && i == ((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10) + ((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10) + (i % 10)*(i % 10)*(i % 10)){
			printf("%d\n", i);
		}
		if (n == 4 && i == ((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10) + ((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10) + ((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10) + (i % 10)*(i % 10)*(i % 10)*(i % 10)){
			printf("%d\n", i);
		}
		if (n == 5 && i == ((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10) + ((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10) + ((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10) + ((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10) + (i % 10)*(i % 10)*(i % 10)*(i % 10)*(i % 10)){
			printf("%d\n", i);
		}
		if (n == 6 && i == ((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10) + ((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10) + ((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10) + ((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10) + ((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10) + (i % 10)*(i % 10)*(i % 10)*(i % 10)*(i % 10)*(i % 10)){
			printf("%d\n", i);
		}
		if (n == 7 && i == ((i / 1000000) % 10)*((i / 1000000) % 10)*((i / 1000000) % 10)*((i / 1000000) % 10)*((i / 1000000) % 10)*((i / 1000000) % 10)*((i / 1000000) % 10) + ((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10) + ((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10) + ((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10) + ((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10) + ((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10) + (i % 10)*(i % 10)*(i % 10)*(i % 10)*(i % 10)*(i % 10)*(i % 10)){
			printf("%d\n", i);
		}
	}
	system("pause");
	return 0;
}

虽然代码看起来很长,但是有效地减少了运行时间
7-4 水仙花数
注:其实用七重循环嵌套来做也是可以的通过的,只要你将pow()函数改成乘号。

相关标签: PTA题目 c语言