VPF::[Паскаль] Разложение числа на сумму кубов

mr.Anderson

Дата 19.10.2008, 15:49 (ссылка)

(нет голосов)

Загрузка ...

iOS Lead Developer

Профиль
Группа: Участник Клуба
Сообщений: 3374
Регистрация: 20.12.2004
Где: далеко

Репутация: 16
Всего: 128

Задача звучит следующим образом.

Цитата

Найти минимальное натуральное число N, которое можно представить 2 разными способами в виде суммы кубов двух натуральных чисел x^3 + y^3 (x>=y).

Я понял так, что число должно быть разложено, допустим, как 3 и 8 в кубе и, к примеру, 4 и 5 в кубе (т.е. должны получиться две различных пары чисел).

Я написал следующий код:

Код


program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

function FindCubeSum(N, X1, X2: Integer; var I1, I2: Integer): Boolean;
var
  I: Integer;
  J: Integer;
  L: Integer;
  Z1: Integer;
  Z2: Integer;
begin
  Result := False;

  if (X1 <> -1) then
    L := X1 + 1
  else L := 1;

  for I := L to (N shr 1)+1 do
  begin
    for J := 2 to I do
    begin  
      if (J = X2) then
        continue;

      Z1 := I*I*I;
      Z2 := J*J*J;

      if (Z1 + Z2) = N then
      begin
        I1 := I;
        I2 := J;
        Result := True;
        exit;
      end
      else
        if (Z1 + Z2) > N then
           exit;
    end;
  end;
end;

var
  N: Integer;
  I: Integer;
  J: Integer;
  X: Integer;
  Y: Integer;

begin
  N := 1;

 while (true) do
 begin
   Inc(N);

   if FindCubeSum(N, -1, -1, I, J) then
     if FindCubeSum(N, I, J, X, Y) then
       break;
 end;

 WriteLn(N, ' = ', I, '^3 + ', J, '^3');
 WriteLn(N, ' = ', X, '^3 + ', Y, '^3');

 ReadLn;
end.

Работает по след. принципу. В бесконечном цикле для последовательно увеличивающегося числа функция ищет метод разложения. В случае удачи эта же функция снова ищет метод разложения, но уже не включает в поиск только что найденную пару. Сам принципе вроде бы правильный. Однако, я программу запускал на довольно длительное время, но результатов никаких не получал. Когда анализируемое число перевалило за 2 миллиарда, я остановился.

Я вот думаю, а вообще такое число существует?

Это сообщение отредактировал(а) mr.Anderson - 19.10.2008, 15:51

--------------------

Aloha

Дата 19.10.2008, 16:56 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 351
Регистрация: 14.5.2006

Репутация: 97
Всего: 165

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

2^3 + 16^3 = 9^3 + 15^3 = 4104

Только не спрашивай как это получилось smile

Вот еще несколько пар:

2^3 + 24^3 = 18^3 + 20^3 = 13832

10^3 + 27^3 = 19^3 + 24^3 = 20683

4^3 + 32^3 = 18^3 + 30^3 = 32832

2^3 + 34^3 = 15^3 + 33^3 = 39312

9^3 + 34^3 = 16^3 + 33^3 = 40033

3^3 + 36^3 = 27^3 + 30^3 = 46683

17^3 + 39^3 = 26^3 + 36^3 = 64232

12^3 + 40^3 = 31^3 + 33^3 = 65728

Это сообщение отредактировал(а) Aloha - 19.10.2008, 17:10

mr.Anderson

Дата 19.10.2008, 17:05 (ссылка)

(нет голосов)

Загрузка ...

iOS Lead Developer

Профиль
Группа: Участник Клуба
Сообщений: 3374
Регистрация: 20.12.2004
Где: далеко

Репутация: 16
Всего: 128

Aloha, как это получилось! Как вы сосчитали! Елки ж...

Добавлено через 1 минуту и 23 секунды
И почему тогда у меня не получается...

*уполз в отладчик*

Добавлено через 14 минут и 32 секунды
Я нашел ошибку! smile

Aloha, +1 !

А как вы нашли эти числа, можете сказать?

--------------------

mr.Anderson

Дата 19.10.2008, 17:41 (ссылка)

(нет голосов)

Загрузка ...

iOS Lead Developer

Профиль
Группа: Участник Клуба
Сообщений: 3374
Регистрация: 20.12.2004
Где: далеко

Репутация: 16
Всего: 128

Кстати, вот исправленный и малость модифицированный код. Может, пригодится кому. Код из Delphi 7.

Aloha, ну так как вы посчитали-то? smile

Интересно очень.

Код


program Project1;

{$APPTYPE CONSOLE}

function FindCubeSum(N, X1, X2: Integer; var I1, I2: Integer): Boolean;
var
  I: Integer;
  J: Integer;
  L: Integer;
  Z1: Integer;
  Z2: Integer;
begin
  Result := False;

  if (X1 <> -1) then             //1729 = 10^3 + 9^3 =
    L := X1 + 1                  //     = 12^3 + 1^3
  else L := 1;

  for I := L to (N shr 1 shr 1)+1 do
  begin
    for J := 1 to I do
    begin
      if (J = X2) then
        continue;

      Z1 := I*I*I;
      Z2 := J*J*J;
      if (Z1 + Z2) = N then
      begin
        I1 := I;
        I2 := J;
        Result := True;
        exit;
      end;
    end;
  end;
end;

var
  N: Integer;
  I: Integer;
  J: Integer;
  X: Integer;
  Y: Integer;
  F: Integer;

begin
  N := 1;

  repeat
    while (true) do
    begin
      Inc(N);

      if FindCubeSum(N, -1, -1, I, J) then
        if FindCubeSum(N, I, J, X, Y) then
          break;
    end;

    WriteLn(N, ' = ', I, '^3 + ', J, '^3');
    WriteLn(N, ' = ', X, '^3 + ', Y, '^3');

    WriteLn;
    Write('Should program try to find next number? Write 1 to continue or 0 to exit: ');
    ReadLn(F);
  until (F = 0);
end.

--------------------

THandle

Дата 19.10.2008, 19:44 (ссылка)

(нет голосов)

Загрузка ...

Хранитель Клуба
Group Icon

Награды: 1

Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: 30
Всего: 372

mr.Anderson, вообще честно говоря в твоем коде разобраться очень сложно... Из за имен переменных таких smile

Назови их хоть по разному(в процедурке и основные), а то мозг отказывается воспринимать. smile

Для будущих покалений лучше оставлять что-то с более осмысленными названиями.... Сорри за оффтоп smile

mr.Anderson

Дата 19.10.2008, 19:49 (ссылка)

(нет голосов)

Загрузка ...

iOS Lead Developer

Профиль
Группа: Участник Клуба
Сообщений: 3374
Регистрация: 20.12.2004
Где: далеко

Репутация: 16
Всего: 128

THandle, код делался для себя, поэтому об именах особо не думал, делал так, чтоб покороче. smile

Я лучше поясню, для чего каждая.

Цитата

В функции.

Аргументы (по порядку): само число, ограничитель 1, ограничитель 2 (для X и Y соответственно), число 1 и число 2, куда запишем результат работы функции.

Переменные: счетчики (I и J), стартовое значение для I, временные переменные для кубов числа I и числа J соответственно.

В основной программе.

Переменные: обрабатываемое число, I и J - первая пара найденных чисел, X и Y - вторая пара, F - флажок для выяснения, нужно продолжать работу программы или нет.

Воть.

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »