Поиск номеров такси

Ответ 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).

Ответ 2

Ниже представлен еще лучший код java для печати номеров N ramanujan, поскольку он имеет еще меньшую временную сложность. Потому что он имеет только один цикл.

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

Ответ 3

EDIT: для тех, кто не знает, что такое 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
и так далее!

Ответ 4

Быстрый и наивный алгоритм (если я правильно понимаю проблему):

Пусть вычислить кубы всех туземцев целых чисел от 1 до N; затем вычисляет все суммы двух кубов. Эти суммы могут храниться в треугольной матрице; не заполняйте всю квадратную матрицу. Наконец, найдите неповторимые элементы в вашей треугольной матрице, это самые номера HR (если вы позволите мне называть числа, которые мы хотим вычислить так). Более того, сортируя массив, сохраняя исходные индексы, вы легко можете найти разложения такого числа.

У моего решения небольшой недостаток: я не знаю, как исправить N в зависимости от вашего ввода n, то есть сколько кубов я должен вычислить, чтобы иметь хотя бы n номеров HR? Осталась интересная проблема.

Ответ 5

Лучший алгоритм, чем выше, чем Никхита Редди. Нам не нужно проверять (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;
}

  }

Ссылка: блог

Ответ 6

Это решение (в 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

Ответ 7

Существует два способа написать решение в 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).