14

找到第一个n出租车号码。给定一个值n。我想找到前 n 个出租车号码。出租车是一个可以用不止一种方式表示为两个完美立方体之和的数字。

（请注意，有两个相关但不同 的集合称为“出租车号码”：2 个多维数据集 的总和，以及 2个正整数立方的总和的最小数字n。这个问题是关于前一组，因为后一组只有前六个成员已知）

例如：

1^3 + 12^3 = 1729 = 9^3 + 10^3

我想大致了解一下算法或如何解决问题的 C 代码片段。

The first five of these are:

   I    J      K    L      Number 
---------------------------------
   1   12      9   10      1729       
   2   16      9   15      4104      
   2   24     18   20     13832       
  10   27     19   24     20683      
   4   32     18   30     32832
4

7 回答 7

11

下面是用于打印 N ramanujan 数字的更好的 Java 代码，因为它的时间复杂度更低。因为，它只有一个 for 循环。

import java.util.*;
public class SolutionRamanujan 
{
    public static void main(String args[] ) throws Exception 
    {
        SolutionRamanujan s=new SolutionRamanujan();
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int i=0,k=1;
        while(i<n){
            if(s.checkRamanujan(k))
            {
                i=i+1;
                System.out.println(i+" th ramanujan number is "+k);
            }
            k++;
        }
        scan.close();
    }
    //checking whether a number is ramanujan number
    public boolean checkRamanujan(int a)
    {   
        int count=0;
        int cbrt=(int)Math.cbrt(a);
        //numbers only below and equal to cube th root of number
        for(int i=1;i<=cbrt;i++)
        {
            int difference=a-(i*i*i);
            int a1=(int) Math.cbrt(difference);                //checking whether the difference is perfect cube 

            if(a1==Math.cbrt(difference)){
                count=count+1;
            }
            if(count>2){            //checking if two such pairs exists i.e. (a*a*a)+(b*b*b)=(c*c*c)+(d*d*d)=number
                return true;
            }
        }
        return false;
    }
}
于 2014-03-07T04:49:42.167 回答
9

我发现可以通过以下方式获得答案：

#include<stdio.h>

int main() {
    int n, i, count=0, j, k, int_count;
    printf("Enter the number of values needed: ");
    scanf("%d", &n);
    i = 1;
    while(count < n) {
       int_count = 0;
       for (j=1; j<=pow(i, 1.0/3); j++) {
          for(k=j+1; k<=pow(i,1.0/3); k++) {
              if(j*j*j+k*k*k == i)
              int_count++;
          }
       }
       if(int_count == 2) {
          count++;
          printf("\nGot %d Hardy-Ramanujan numbers %d", count, i);  
       }
       i++;
    }
}

既然a^3+b^3 = n，a应该小于n^(1/3)。

于 2012-07-14T08:39:38.010 回答
3

编辑：对于那些不知道 R 是什么的人，这里有一个链接。

我的 C 有点生疏……我会用 R 写一个解决方案，应该不难适应。该解决方案在 R 中运行得非常快，因此在 C 中应该更快。

# Create an hash table of cubes from 1 to 100

numbers <- 1:100
cubes <- numbers ^ 3

# The possible pairs of numbers
pairs <- combn(numbers, 2)

# Now sum the cubes of the combinations
# This takes every couple and sums the values of the cubes
# with the appropriate index 
sums <- apply(pairs, 2, function(x){sum(cubes[x])})

所以：

numbers将是：1, 2, 3, 4, ..., 98, 99, 100
cubes将是：1, 8, 27, 64, ..., 941192, 970299, 1000000
pairs将包含：

     [,1] [,2] [,3] [,4] [,5] ... [,4949] [,4950]
[1,]    1    1    1    1    1 ...      98      99
[2,]    2    3    4    5    6 ...     100     100

sums将会：9 28 65 126 217 344 ... 1911491 1941192 1970299

快速检查我们是否在正确的轨道上......

> which(sums == 1729)
[1]  11 765  <--- the ids of the couples summing to 1729
> pairs[,11]
[1]  1 12
> pairs[,765]
[1]  9 10

现在，让我们找出哪些是总和相同的夫妇。

table(sums)给我们一个简洁的总结，比如

> 9 28 35 65 72 91 ...                        1674 1729 1736    
  1  1  1  1  1  1 .... <lots of 1s here> ...    1    2    1

所以我们只需要找出哪些元素table(sums)是 == 2

doubles <- which(table(sums) == 2)

taxi.numbers <- as.integer(names(doubles))
 [1]    1729    4104   13832   20683   32832   39312   40033   46683   64232   65728
[11]  110656  110808  134379  149389  165464  171288  195841  216027  216125  262656
[21]  314496  320264  327763  373464  402597  439101  443889  513000  513856  515375
[31]  525824  558441  593047  684019  704977  805688  842751  885248  886464  920673
[41]  955016  984067  994688 1009736 1016496

最后（两两读取）对应的整数对

> pairs[,doubles]
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15]
[1,]    1    9    2    9    2   18   10   19    4    18     2    15     9    16     3
[2,]   12   10   16   15   24   20   27   24   32    30    34    33    34    33    36
     [,16] [,17] [,18] [,19] [,20] [,21] [,22] [,23] [,24] [,25] [,26] [,27] [,28] [,29]
[1,]    27    17    26    12    31     4    36     6    27    12    38     8    29    20
[2,]    30    39    36    40    33    48    40    48    45    51    43    53    50    54
     [,30] [,31] [,32] [,33] [,34] [,35] [,36] [,37] [,38] [,39] [,40] [,41] [,42] [,43]
[1,]    38    17    24     9    22     3    22     5    45     8    36     4    30    18
[2,]    48    55    54    58    57    60    59    60    50    64    60    68    66    68
     [,44] [,45] [,46] [,47] [,48] [,49] [,50] [,51] [,52] [,53] [,54] [,55] [,56] [,57]
[1,]    32    30    51     6    54    42    56     5    48    17    38    10    45    34
[2,]    66    67    58    72    60    69    61    76    69    76    73    80    75    78
     [,58] [,59] [,60] [,61] [,62] [,63] [,64] [,65] [,66] [,67] [,68] [,69] [,70] [,71]
[1,]    52    15    54    24    62    30    57     7    63    51    64     2    41    11
[2,]    72    80    71    80    66    81    72    84    70    82    75    89    86    93
     [,72] [,73] [,74] [,75] [,76] [,77] [,78] [,79] [,80] [,81] [,82] [,83] [,84] [,85]
[1,]    30    23    63     8    72    12    54    20    33    24    63    35    59    29
[2,]    92    94    84    96    80    96    90    97    96    98    89    98    92    99
     [,86] [,87] [,88] [,89] [,90]
[1,]    60    50    59    47    66
[2,]    92    96    93    97    90

所以：

1,12 和 9,10 给 1729
2,16 和 9,15 给 4104
2,24 和 18,20 给 13832
等等！

于 2012-07-10T10:41:19.770 回答
3

快速而幼稚的算法（如果我正确理解了问题）：

让我们计算从 1 到 N 的所有原生整数的立方；然后计算两个立方体的所有总和。这些和可以存储在三角矩阵中；避免填充整个方阵。最后，在你的三角矩阵中找到非唯一元素，这些就是 HR 数字（如果你让我这样称呼我们想要计算的数字）。此外，通过在保留原始索引的同时对数组进行排序，您可以轻松推断出这样一个数字的分解。

我的解决方案有一个小缺陷：我不知道如何根据您的输入 n 来修复 N，即我必须计算多少个立方体才能获得至少 n 个 HR 数字？留下有趣的问题。

于 2012-07-10T10:58:41.643 回答
1

比上面的 Nikhitha Reddy 更好的算法。我们不必同时检查 (i,j) 和 (j,i) 。

这是Java代码。

import java.util.*;

public class efficientRamanujan{

public static void main(String[] args) {
    efficientRamanujan s=new efficientRamanujan();
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int i=0,k=1;
        while(i<n){
           if(s.efficientRamanujan(k))
        {
            i=i+1;
            System.out.println(i+" th ramanujan number is "+k);
        }
        k++;
    }
    scan.close();
   }






public boolean efficientRamanujan(int n){
    int count=0;

    int x = 1;
    int y = (int) Math.cbrt(n);

    while (x<y){

        int sum = (int) Math.pow(x,3) + (int) Math.pow(y,3);
        if(sum<n){
           x = x+1;
        }else if(sum>n){
           y = y-1;
        }else{
           count++;
           x = x+1;
           y = y-1;
    }

    if(count>=2){
        return true;
    }
}

return false;
}

  }

参考： 博客

于 2016-01-21T16:38:12.800 回答
0

此解决方案（在 python 中）以自下而上的方法生成第一个 n 出租车号码。时间复杂度为 m^2，其中 m 是生成 n 个数字的最高数字。

def generate_taxi_cab_numbers(n):
    generated_number = 0
    v = {}
    c = {}
    i = 0
    while generated_number < n:
        c[i] = i*i*i
        for j in xrange(i):
            s = c[j] + c[i]
            if s in v:
                generated_number = generated_number + 1
                yield (s, (j, i), v[s])
            v[s] = (j,i)
        i = i + 1


def m(n):
    for x in generate_taxi_cab_numbers(n):
       print x
于 2015-03-04T16:02:22.357 回答
0

用 Python 编写解决方案有两种方法：动态编程和蛮力。

def ramanujanDynamicProgramming(n):
    numbers = []
    Ds = dict()

    # Init List
    for d in xrange(0, n ** 3):
        Ds[d] = False

    # Fill list
    for d in xrange(0, n):
        Ds[d**3] = d

    for a in xrange(0, n):
        for b in xrange(0, n):
            for c in xrange(0, n):

                if a != b and a != c and b != c:
                    d = a ** 3 + b ** 3 - c ** 3

                    if a != d and b != d and c != d and d >= 0 and d < n ** 3:
                        if Ds[d] != False:
                            numbers.append((a, b, c, Ds[d]))

        return numbers 
print "Dynamic Programming"
print ramanujanDynamicProgramming(n)

DP 方法只需要 O(n^3)。

def ramanujanBruteForce(n):
    numbers = []
    for a in xrange(0, n):
        for b in xrange(0, n):
            for c in xrange(0, n):
                for d in xrange(0, n):
                    if a != b and a != c and a != d and b != c and b != d and c != d:
                        if a ** 3 + b ** 3 == c ** 3 + d ** 3:
                            numbers.append((a, b, c, d))

        return numbers
print "Brute Force"
print ramanujanBruteForce(n)

BF 方法是 BF 是 O(n^4)。

于 2015-05-24T03:05:58.587 回答