如何更快地生成自恋数？ [英] how to generate Narcissistic numbers faster?

问题描述

自恋数字是n个数字，其中所有数字的n次幂的总和等于该数字。

因此， 153 是自恋数字，因为 1 ^ 3 + 5 ^ 3 + 3 ^ 3 = 153 。

现在给定N，找到N个数字长度的所有自恋数字？

我的方法对于所有数字执行数字的幂的总和

并检查其是否相同的数字，并且我计算的权力。

$

更新：
在自然界中只有88个自恋数字，最大的是39个数字，
但我只需要长度为12或更少的数字。

代码：

  long long int powers [11] [12] 
 // powers [x] [y]是x ^ y。和它已经计算的
 
 bool isNarcissistic（long long int x，int n）{
 long long int r = x; 
 long long int sum = 0; 
 
 for（int i = 0; i  sum + = powers [x％10] [n]; 
 if（sum> r）
 return false; 
 x / = 10; 
} 
 return（sum == r）; 
} 
 
 void find（int n，vector< long long int>& vv）{
 long long int start = powers [10] [n-1] 
 long long int end = powers [10] [n]; 
 
 for（long long int i = start; i  if（isNarcissistic（i，n））
 vv.push_back 
} 
} 
  

解决方案

下面的代码实现了@Daniel Fischer的想法。它会复制在Mathworld上引用的表格，然后打印几个11位数字，并验证没有12个数字按此处说明数字。

它实际上会更简单，可能会更快地生成非增长数字字符串的所有可能的直方图，而不是字符串本身。通过直方图，我意味着以相应数字的频率的0-9为索引的表。这些可以直接比较而不排序。但是下面的代码运行在& 1秒，所以我不会实现直方图的想法。

  #include< stdio.h> 
 #include< stdlib.h> 
 #include< string.h> 
 
 #define MAX_DIGITS 12 
 
 // pwr [d] [n] is d ^ n 
 long long pwr [10] [MAX_DIGITS + 1]; 
 
 //正在考虑的数字的数字和最终索引。 
 int digits [MAX_DIGITS]; 
 int m; 
 
 //填充pwr。 
 void fill_tbls（void）
 {
 for（int d = 0; d <10; d ++）{
 pwr [d] [0] 
 for（int p = 1; p <= MAX_DIGITS; p ++）
 pwr [d] [p] = pwr [d] [p-1] * d; 
} 
} 
 
 //整数递减的整数的整数比较
 int cmp_ints_desc（const void * vpa，const void * vpb）
 {
 const int * pa = vpa，* pb = vpb; 
 return * pb  -  * pa; 
} 
 
 //测试当前号码，如果是自恋则打印。 
 void test（void）
 {
 long long sum = 0; 
 for（int i = 0; i <= m; i ++）
 sum + = pwr [digits [i]] [m + 1]; 
 int sum_digits [MAX_DIGITS * 2]; 
 int n = 0; 
 for（long long s = sum; s; s / = 10）
 sum_digits [n ++] = s％10; 
 if（n == m + 1）{
 qsort（sum_digits，n，sizeof（int），cmp_ints_desc）; 
 if（memcmp（sum_digits，digits，n * sizeof（int））== 0）
 printf（％lld\\\
，sum）; 
} 
} 
 
 //非递增数字字符串的递归生成器。 
 //当字符串完成时调用测试。 
 void gen（int i，int min，int max）
 {
 if（i> m）
 test 
 else {
 for（int d = min; d <= max; d ++）{
 digits [i] = d; 
 gen（i + 1,0，d）; 
} 
} 
} 
 
 //填充表并生成。 
 int main（void）
 {
 fill_tbls（）; 
 for（m = 0; m  gen（0,1，9）; 
 return 0; 
} 
  

The "Narcissistic numbers", are n digit numbers where the sum of all the nth power of their digits is equal to the number.

So, 153 is a narcissistic number because 1^3 + 5^3 + 3^3 = 153.

Now given N, find all Narcissistic numbers that are N digit length ?

My Approach : was to iterate over all numbers doing sum of powers of digits

and check if its the same number or not, and I per calculated the powers.

but that's not good enough, so is there any faster way ?!

Update: In nature there is just 88 narcissistic numbers, and the largest is 39 digits long, But I just need the numbers with length 12 or less.

My Code :

long long int powers[11][12];
// powers[x][y] is x^y. and its already calculated

bool isNarcissistic(long long int x,int n){
    long long int r = x;
    long long int sum = 0;

    for(int i=0; i<n ; ++i){
        sum += powers[x%10][n];
        if(sum > r)
            return false;
        x /= 10;
    }
    return (sum == r);
}

void find(int n,vector<long long int> &vv){
    long long int start = powers[10][n-1];
    long long int end = powers[10][n];

    for(long long int i=start ; i<end ; ++i){
        if(isNarcissistic(i,n))
            vv.push_back(i);
    }
}

解决方案

The code below implements the idea of @Daniel Fischer. It duplicates the table referenced at Mathworld and then prints a few more 11-digit numbers and verifies that there are none with 12 digits as stated here.

It would actually be simplier and probably a little faster to generate all possible histograms of non-increasing digit strings rather than the strings themselves. By a histogram I mean a table indexed 0-9 of frequencies of the respective digit. These can be compared directly without sorting. But the code below runs in < 1 sec, so I'm not going to implement the histogram idea.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_DIGITS 12

// pwr[d][n] is d^n
long long pwr[10][MAX_DIGITS + 1];

// Digits and final index of number being considered.
int digits[MAX_DIGITS];
int m;

// Fill pwr.
void fill_tbls(void)
{
  for (int d = 0; d < 10; d++) {
    pwr[d][0] = 1;
    for (int p = 1; p <= MAX_DIGITS; p++) 
      pwr[d][p] = pwr[d][p-1] * d;
  }
}

// qsort comparison for integers descending
int cmp_ints_desc(const void *vpa, const void *vpb)
{
  const int *pa = vpa, *pb = vpb;
  return *pb - *pa;
}

// Test current number and print if narcissistic.
void test(void)
{
  long long sum = 0;
  for (int i = 0; i <= m; i++)
    sum += pwr[digits[i]][m + 1];
  int sum_digits[MAX_DIGITS * 2];
  int n = 0;
  for (long long s = sum; s; s /= 10)
    sum_digits[n++] = s % 10;
  if (n == m + 1) {
    qsort(sum_digits, n, sizeof(int), cmp_ints_desc);
    if (memcmp(sum_digits, digits, n * sizeof(int)) == 0) 
      printf("%lld\n", sum);
  }
}

// Recursive generator of non-increasing digit strings.
// Calls test when a string is complete.
void gen(int i, int min, int max)
{
  if (i > m) 
    test();
  else {
    for (int d = min; d <= max; d++) {
      digits[i] = d;
      gen(i + 1, 0, d); 
    }
  }
}

// Fill tables and generate.
int main(void)
{
  fill_tbls();
  for (m = 0; m < MAX_DIGITS; m++)
    gen(0, 1, 9);
  return 0;
}

这篇关于如何更快地生成自恋数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！