C++程序 检查阿姆斯特朗数
给定一个数字 x ,确定给定的数字是否是 阿姆斯特朗数 。
如果一个有 n 个数位的正整数 被称为 n阶阿姆斯特朗数 (order是数字数位),那么:
abcd… = pow(a,n) + pow(b,n) + pow(c,n) + pow(d,n) + ….
示例:
输入: 153
输出: Yes
153是一个阿姆斯特朗数。
1*1*1 + 5*5*5 + 3*3*3 = 153
输入: 120
输出: No
120不是一个阿姆斯特朗数。
1*1*1 + 2*2*2 + 0*0*0 = 9
输入: 1253
输出: No
1253不是一个阿姆斯特朗数。
1*1*1*1 + 2*2*2*2 + 5*5*5*5 + 3*3*3*3 = 723
输入: 1634
输出: Yes
1*1*1*1 + 6*6*6*6 + 3*3*3*3 + 4*4*4*4 = 1634
方法: 思路是先计算数字位数(或找到阶),将数字x中的每个数字r乘以n次方。如果所有这些值的总和等于n,则返回true,否则返回false。
//确定数字是阿姆斯特朗数还是不是
#include <bits/stdc++.h>
using namespace std;
//计算x的y次方
int power(int x, unsigned int y)
{
if (y == 0)
return 1;
if (y % 2 == 0)
return (power(x, y / 2) *
power(x, y / 2));
return (x * power(x, y / 2) *
power(x, y / 2));
}
//计算数字的阶
int order(int x)
{
int n = 0;
while (x)
{
n++;
x = x / 10;
}
return n;
}
//检查数字是否是阿姆斯特朗数
bool isArmstrong(int x)
{
// 调用order函数
int n = order(x);
int temp = x, sum = 0;
while (temp)
{
int r = temp % 10;
sum += power(r, n);
temp = temp / 10;
}
// 满足Armstrong 条件
return (sum == x);
}
// 驱动程序
int main()
{
int x = 153;
cout << boolalpha <<
isArmstrong(x) <<
endl;
x = 1253;
cout << boolalpha <<
isArmstrong(x) <<
endl;
return 0;
}
输出:
true
false
时间复杂度: O(log 2 n) + O((log 10 n)*(log 2 d)),其中n是要检查的数字,d是输入数字的位数。
空间复杂度: O(log 2 d),其中d是数字的位数。
上述方法也可以以更短的方式实现:
// C++实现以上方法程序
#include<iostream>
using namespace std;
// 主函数
int main()
{
int n = 153;
int temp = n;
int p = 0;
// 计算数字各位数的和
while (n > 0)
{
int rem = n % 10;
p = (p) + (rem * rem * rem);
n = n / 10;
}
// 判断是否为阿姆斯特朗数
if (temp == p)
{
cout << ("是阿姆斯特朗数。");
}
else
{
cout << ("不是阿姆斯特朗数。");
}
return 0;
}
// 本代码由 sathiyamoorthics19 提供```
输出:
是阿姆斯特朗数。
给定程序的时间复杂度为O(d),其中d是n输入数字的位数。这由于while循环运行’d’迭代,在每个迭代中执行常量时间操作。
程序的空间复杂度为O(1),因为仅使用了少量整数变量并且不需要使用数组、链表或其他数据结构的额外空间。
找到第n个阿姆斯特朗数
输入: 9
输出: 9
输入: 10
输出 : 153
// C++程序用于查找第n个Armstrong Number
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
// 功能:查找第n个阿姆斯特朗数
int NthArmstrong(int n)
{
int count = 0;
// i从整数 1 开始到 INT_MAX结束
for (int i = 1; i <= INT_MAX; i++)
{
int num = i, rem, digit = 0, sum = 0;
// 将i的值复制到num
num = i;
// 计算num中的总数字数
digit = (int)log10(num) + 1;
// 计算数字幂的总和
while (num > 0)
{
rem = num % 10;
sum = sum + pow(rem, digit);
num = num / 10;
}
// 检查是否为阿姆斯特朗数
if (i == sum)
count++;
if (count == n)
return i;
}
}
// 主函数
int main()
{
int n = 12;
cout << NthArmstrong(n);
return 0;
}
// 本代码由'jaingyayak'提供```
输出:
371