寻找出租车号码
找到前n出租车编号。 给定值n 。 我想找到前n个出租车编号。 出租车是一个数字，可以用不止一种方式表示为两个完美立方体的总和。
（注意，有两个相关但不同的集合称为’出租车编号’： 2个立方体的总和超过1种方式 ， 最小的数字是2个正整数立方体的总和，用
n种方式 。这个问题是关于前一组，因为后一组只有前六名成员知道）
例如：
1^3 + 12^3 = 1729 = 9^3 + 10^3
我想粗略概述算法或如何解决问题的C片段。
The first five of these are: IJKL 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
下面是用于打印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(i2){ //checking if two such pairs exists ie (a*a*a)+(b*b*b)=(c*c*c)+(d*d*d)=number return true; } } return false; } }
我想出答案可以通过这种方式获得：
#include 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) 。
快速而天真的算法（如果我正确理解问题）：
让我们计算从1到N的所有本地整数的立方体; 然后计算两个立方体的所有总和。 这些总和可以存储在三角矩阵中; 避免填充整个方阵。 最后，找到三角矩阵中的非唯一元素，这些是非常HR的数字（如果你让我调用我们想要计算的数字，就像这样）。 此外，通过在保持原始索引的同时对数组进行排序，您可以轻松推断出这种数字的分解。
我的解决方案有一点缺陷：我不知道如何修复N取决于你的输入n，即我必须计算多少立方体才能拥有至少n个HR数字？ 有趣的问题离开了。
编辑 ：对于那些不知道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 .... ... 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
等等！
比上面的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(in){ y = y-1; }else{ count++; x = x+1; y = y-1; } if(count>=2){ return true; } } return false; } }
参考： 博客
这个解决方案（在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
在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）。