Блог

У меня есть программа TaxiCab number, реализованная как на Python, так и на C , я не понимаю, почему один и тот же код выдает разные результаты, может кто-нибудь просветить меня о работе этих циклов.

Проверьте выходные данные кодов, оба языка пропустили определенные пары ответов.

 #include <iostream>
#include <cmath>
#include <ctime>
#include "iomanip"

using namespace std;

int ramanujan(int n) {
  int count = 0;
  int i = 0;
  int x;
  int y;
  std::cout << "Inside Ramanujan Function and outn";
  std::cout << setw(10) << "a" << setw(10) << "b" << setw(10) << "c" << setw(10)
            << "d" << setw(20) << "TaxiCab" << 'n';
  std::cout << "n"; // Needless to say you can ignore cout<<
  for (i = 1; i < n; i  ) {
    for (int j = i   1; j < n; j  ) {
      for (int a = i   2; a < n; a  ) {
        for (int b = a; b < n; b  ) {
          x = std::pow(i, 3)   std::pow(j, 3);
          y = std::pow(a, 3)   std::pow(b, 3);
          if (x == y amp;amp; i != j amp;amp; i != b amp;amp; i != a amp;amp; j != a amp;amp; j != b amp;amp;
              a != b) {
            std::cout << setw(10) << i << setw(10) << j << setw(10) << a
                      << setw(10) << b << setw(20) << x << 'n';
            count = count   1;
            if (count > 15) {
              return 0;
            }
          }
        }
      }
    }
  }
  return 1;
}

int main() {
  clock_t begin = clock();
  ramanujan(50);
  std::cout << "Done!n";
  clock_t end = clock();
  double timeSec = (end - begin) / static_cast<double>(CLOCKS_PER_SEC);
  std::cout << timeSec << " Seconds taken";
}
  

Версия Python

 import time
from numba import njit


@njit  # Comment this line if there is a Numba error
def ramanujan(n):
    count = 0
    print("a   b    c    d    TaxiCab")
    for x in range(1, n):
        for y in range(x, n):
            for a in range(x, n):
                for b in range(a, n):  # Python for loops

                    z = (x ** 3)   (y ** 3)
                    z2 = (a ** 3)   (b ** 3)

                    if (
                        z == z2
                        and x != y
                        and x != a
                        and x != b
                        and y != a
                        and y != b
                        and a != b
                    ):
                        print(x, y, a, b, z)
                        count = count   1
                        if count > 15:
                            return  # Breaks all for loops once 10 such pairs are found


# Dont worry about the problem setup

start = time.time()
ramanujan(50)
print("Done")
end = time.time()
print(end - start)

  

Использование std::pow для оценки мощности целых чисел подвержено ошибкам округления из-за ограниченной точности чисел с плавающей запятой.

Лучший (и, вероятно, более быстрый) подход, если требуется точное значение и нет риска переполнения диапазона целочисленных значений, заключается в использовании простых умножений.

Ниже также приведен немного улучшенный (ИМХО) алгоритм решения проблемы OP, если я правильно понял.

 #include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>

int ramanujan(int n)
{    
    using std::setw;
    // Evaluate all the possible pairs and collect the sums
    std::map<long, std::vector<std::pair<int, int>>> sums;
    for (int i = 1; i <= n; i  ) {
        for (int j = i   1; j <= n; j  ) {
            auto sum =  long(i) * i * i   long(j) * j * j;
            auto it = sums.find(sum);
            if ( it != sums.end() )
                it->second.emplace_back(i, j);
            else
                sums.emplace(sum, std::vector<std::pair<int, int>>{{i, j}});
        }
    }

    // Now print only the sums of powers (sorted) that
    // are generated by more then one couple
    int count = 0;
    std::cout << setw(8) << "a" << setw(8) << "b"
              << setw(8) << "c" << setw(8) << "d" << setw(16) << "TaxiCab" << 'n'
              << "------------------------------------------------------n";
    for (auto const amp; i : sums)
    {
        if ( i.second.size() > 1 )
        {
              count;
            std::cout << setw(8) << i.second[0].first     // a
                      << setw(8) << i.second[0].second    // b
                      << setw(8) << i.second[1].first     // c
                      << setw(8) << i.second[1].second    // d
                      << setw(16) << i.first << 'n';     // a^3   b^3 (= c^3   d^3)
        }
    }
    return count;
}
  

Который, если будет передано 50, выведет

 a b c d Такси
------------------------------------------------------
 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
 2 34 15 33 39312
 9 34 16 33 40033
 3 36 27 30 46683
 17 39 26 36 64232
 12 40 31 33 65728
 4 48 36 40 110656
 6 48 27 45 110808
Готово!

Проблема была связана с ошибками округления, вызванными функцией std::pow(x,n) . Он возвращает число с плавающей запятой и вызывает ошибки округления. Заменив его pow(i,3) на long (i) i я решил проблему.

Кто-нибудь может прокомментировать, почему такая ошибка округления не была проблемой для Python?