查找出租車計費號碼

Question

查找首個n出租車計程車號碼。給定值n。我想找到前n個計程車號碼。 出租車是一個數字，可以用多種方式表示爲兩個完美立方體的總和。

（請注意，有兩個相關但不同的被稱爲 「的士數」集：在sums of 2 cubes in more than 1 way，並the smallest numbers that are the sum of 2 positive integral cubes in n ways這個問題是關於前集， 因爲後者集只有第一已知的六個成員）

例如：

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

我想ALG的粗略綜述行動或如何解決問題的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  

Answer 1

我想出答案，可以通過這種方式獲得：

#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)。

Answer 2

編輯：對於那些誰不知道什麼R是，這裏是一個link。

我的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
等等！

Answer 3

快速和天真的算法（如果我理解正確的問題）：

讓我們計算從1到N的所有當地人整數的立方體;然後計算兩個立方體的所有和。這些和可以存儲在三角矩陣中;避免填充整個方陣。最後，找到三角矩陣中的非唯一元素，這些就是HR數字（如果你讓我打電話給我們想要計算的數字）。此外，通過在保留原始指數的同時對數組進行排序，您可以輕鬆推斷出這樣一個數字的分解。

我的解決方案有一個小缺陷：我不知道如何解決N取決於您的輸入n，那麼我必須計算多少個立方體才能擁有至少n個HR數字？有趣的問題離開了。

Answer 4

下面是打印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; 
    } 
} 

Answer 5

該解決方案（在Python中）以自下而上的方式生成第一個出租車編號。時間複雜度是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 

Answer 6

有兩種方法可以在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）。

Answer 7

比上面的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; 
} 

    } 

參考： blog