Версия для печати темы

Автор: Bard 8.05.2008 15:27

Надо найти число делящееся на 2 в степени 100 и состоящее только из единиц и двоек.
Пока что нашел только 2 в степени 100 которое равно 1267650600228229401496703205376 ... Надо найти просто это число. У кого какие идеи?

Автор: compiler 8.05.2008 16:33

неправильно понял условие...

Автор: volvo 8.05.2008 16:38

Метод индукции. Вот тут объяснение:
http://www.sciteclibrary.ru/cgi-bin/yabb2/YaBB.pl?num=1062572919/2

Автор: andriano 8.05.2008 22:19

На уровне идеи:
Вводим систему считсления по основанию 2, в которой в качестве цифр используем символы "1" и "2".

Автор: Bard 5.06.2008 14:12

volvo, большое спасибо за подсказку и ссылку . Я уже примерно месяц стараюсь решить эту задачу, но никак не получаеться . Мне не удается реализовать рекурсию . Могли бы вы помочь мне в этом деле? заранее большое спасибо.

Автор: volvo 5.06.2008 16:05

Ну, если просто найти число...

Я проверял на FPC (но, в принципе, модуль не содержит ничего криминального и для TP, насколько я вижу, должно работать и там), с использованием модуля HugeInts, описанного в DRKB -> Математика, алгоритмы -> Арифметика, системы счисления, комплексные числа -> Очень большие числа -> Огромные числа:

uses HugeInts;

var
  two, n, divider, r: hugeint;
  s, s_div: string;
  i: integer;

begin
  integer2hugeint(2, two);
  n := two; divider := two;
  for i := 2 to 100 do begin { работаем до 2^100 }

    hugeint_mul(divider, two, divider); { следующая степень двойки }
    hugeint_mod(n, divider, R); { R - остаток от деления N на след. степень 2 }

    hugeint2string(n, s); { Для удобства преобразуем в строку }
    if hugeint_zero® then s := '2' + s { Делится? Значит, добавляем 2 спереди }
    else s := '1' + s; { Не делится? Добавляем 1 }
    string2hugeint(s, n); { Конвертируем назад в HugeInt }

  end;

  HugeInt2String(divider, s_div);
  writeln(s_div);
  HugeInt2String(n, s);
  writeln(s);
end.

А теперь проверяем полученный результат:

uses HugeInts;
var n, R, divider: hugeint;
begin
  string2hugeint('1267650600228229401496703205376', divider);
  string2hugeint(
    '121121121122112121121112112212221121222111212211112'+
    '2212112212121112121121122111112111211111212122112', n);
  hugeint_mod(n, divider, R);

  if hugeint_zero® then writeln('ok')
  else writeln('something wrong!!!');
end.

Это сама идея. Работает довольно медленно, потому что все время эти конвертации... Да, и еще. Запускать программу надо с режимом {$R-}, и заменив там в исходнике модуля HugeIntSize на что-нибудь более серьезное, чем 8 по умолчанию. Я взял HugeIntSize = 1000, чтоб гарантированно избежать переполнения... Но уж никак не меньше 100, поскольку в результате получаем 100-значное число...