c - タクシー数を探す

Question

n最初のタクシー番号を見つけます。与えられた値n。最初のn個のタクシー数を見つけたいと思います。タクシーは、2つの完全な立方体の合計として複数の方法で表現できる数です。

（「タクシー数」と呼ばれる2つの関連するが異なるセットがあることに注意してください：複数の方法で2つの立方体の合計、および方法で2つの正の整数立方体の合計である最小の数n。この質問は前者のセット、後者のセットには最初の6つのメンバーしか知られていないため）

例えば：

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

score 11 · Accepted Answer

以下は、時間計算量がさらに少ないため、Nラマヌジャン数を出力するためのさらに優れたJavaコードです。なぜなら、forループは1つしかないからです。

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;
    }
}

score 9 · Accepted Answer

私は答えがこの方法で得られることができると考えました：

#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ます。an^(1/3)

score 3 · Accepted Answer

編集：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

そして最後に（2 x 2で読み取られる）、対応する整数のペア

> 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は
41042,24と18,20を与えます13832
などを与えます！

score 3 · Accepted Answer

迅速で素朴なアルゴリズム（問題を正しく理解している場合）：

1からNまでのすべてのネイティブ整数の立方体を計算してみましょう。次に、2つのキューブのすべての合計を計算します。これらの合計は三角行列に格納できます。正方行列全体を埋めることは避けてください。最後に、三角行列で一意でない要素を見つけます。これらはまさにHR番号です（このように計算したい番号を呼び出させてください）。さらに、元のインデックスを保持したまま配列をソートすることにより、そのような数の分解を簡単に推測できます。

私のソリューションには少し欠点があります。入力nに応じてNを修正する方法がわかりません。つまり、少なくともn個のHR番号を取得するには、いくつのキューブを計算する必要がありますか？興味深い問題が残っています。

score 1 · Accepted Answer

上記のNikhithaReddyよりも優れたアルゴリズム。（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;
}

  }

参照：ブログ

score 0 · Accepted Answer

このソリューション（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

score 0 · Accepted Answer

Pythonでソリューションを作成するには、動的計画法とブルートフォースの2つの方法があります。

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）です。

c - タクシー数を探す

7 に答える 7

Related

Reference