检查一个数是否为自恋数

自恋数是一种具有独特性质的特殊数字。如果一个数的各位数字分别乘以其自身次方之和等于该数本身，则该数被认为是自恋数。这些数字并不常见，已知的也不多。如果使用定义 00 = 0，则 0 也可以被认为是一个自恋数。

以下文章提供了一种方法来确定一个数是否为自恋数，同时牢记自恋数的这些特性。

问题陈述

手头上的任务是检查给定的整数 n 是否为自恋数，即当每个数字都乘以其自身次方并求和时，结果是否等于原始数字。如果它是自恋数，程序应该返回 true，否则应该返回 false。

示例

Input: 1
Output: True

解释 − (1 的 1 次方) = 11 = 1。

由于结果数字等于原始数字，因此 1 是一个自恋数。

Input: 1603
Output: False

解释 − (1 的 1 次方) + (6 的 6 次方) + (0 的 0 次方) + (3 的 3 次方) = 11 + 66 + 00 + 33 ≠ 1603 。

这等于 46684。由于结果数字不等于原始数字，因此 1603 不是自恋数。

Input: 3435
Output: True

解释 − (3 的 3 次方) + (4 的 4 次方) + (3 的 3 次方) + (5 的 5 次方) = 33 + 44 + 33 + 55 = 3435。

由于结果数字等于原始数字，因此 3435 是一个自恋数。

Input: 4335
Output: False

解释 − (4 的 4 次方) + (3 的 3 次方) + (3 的 3 次方) +(5 的 5 次方) = 44 + 33 + 33 + 55 ≠ 4335。

由于结果数字不等于原始数字，因此 4335 不是自恋数。

解决方案方法

为了确定提供的数字是否为自恋数，我们必须知道每个数字乘以其自身次方之和是否与原始数字相同。以下方法可用于计算总和并确定结果是否与原始数字匹配。

算法

该方法包括以下步骤 −

  • 将给定的数字分解成其各位数字。

  • 将每个数字乘以其自身次方。

  • 将结果相加。

  • 将总和与原始数字进行比较。

  • 显示答案。

伪代码

函数 is_munchhausen()

  • 初始化 sum = 0

  • 初始化 temp = n

  • 当 (temp > 0)

    初始化 digit = temp % 10

    sum = sum + pow(digit, digit)

    temp = temp / 10

  • 返回 sum == n

函数 main()

  • 初始化 n

  • 如果 (is_munchhausen())

    cout << “自恋数”

  • 否则

    cout << “非自恋数”

  • 打印输出

示例：C++ 程序

该程序通过调用 is_munchhausen() 函数来确定一个数是否为自恋数。该函数使用一个等于 n 的临时变量和另一个变量 sum 来存储每个数字乘以其自身次方结果的总和。

在循环的每次迭代中，使用 ‘%’ 运算符访问 temp 的每个个位数字。它返回数字的最右边的数字。然后将该数字乘以其自身次方并添加到 sum 中。在每次迭代结束时，temp 除以 10 以访问下一个数字。循环运行直到 temp > 0。

// C++ code for Münchhausen Number
#include <iostream>
#include <cmath>

using namespace std;
// this function is used to check out whether the given number is Münchhausen Number or not
bool is_munchhausen(int n){
   int sum = 0;
   int temp = n;
   while (temp > 0){
      int digit = temp % 10; //yields the rightmost digit as remainder
      sum = sum + pow(digit, digit);
      temp = temp / 10; // yields the remaining number
   }
   return (sum == n); // returns true if sum is equal to original number
}
// Driver Code
int main(){
   int n = 3253;
   cout << "input number: " << n << endl;
   if (is_munchhausen(n)){
      cout << "Münchhausen Number" << endl;
   } else {
      cout << "Non-Münchhausen Number" << endl;
   }
   return 0;
}

输出

input number: 3253
Non-Münchhausen Number

时间和空间复杂度分析

时间复杂度 − O(log n) 时间复杂度，其中 n 是输入参数的值。这是因为函数 is_munchhausen() 中 while 循环的迭代次数取决于给定数字的位数，这与以 10 为底的对数 log(n) 成正比。该函数在主函数中调用一次，因此程序的整体复杂度与 log(n) 成正比。

空间复杂度 − O(1)。此函数使用固定数量的内存来存储整数变量 sum 和 temp，而不管输入参数的大小如何，因此其空间复杂度是常数。

结论

总之，自恋数是唯一用其各位数字分别乘以其自身次方之和表示的数字。它们并不常见，找到它们可能是一项艰巨的任务。本文讨论的解决方案方法提供了一种方法，可以在对数时间内轻松检查一个数是否为自恋数，而无需使用辅助空间。本文使用各种示例深入解释了自恋数的概念。可以使用附带的 C++ 代码快速确定给定数字是否为自恋数。

更新于： 2023-04-19

547 次浏览

开启您的 职业生涯

通过完成课程获得认证

立即开始
广告