Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 01.05.2008, 08:56   #1
Иллидан
Форумчанин
 
Регистрация: 16.01.2008
Сообщений: 288
По умолчанию Задача на свойства чисел

Задача, найти(за максимально короткое время) сколько чисел в диапазоне от a b(a,b ≤ 10 в 18) имеют хотя бы одну одинаковую противоположную цифру, то есть какое-нибудь Ki = Kn+1−i при i ≠ n+1−i. Наример в диапазоне от 10 до 99 таких чисел 9 (11,22...99) У кого какие предложения?
Иллидан вне форума Ответить с цитированием
Старый 01.05.2008, 09:25   #2
alexBlack
Участник клуба
 
Регистрация: 12.10.2007
Сообщений: 1,204
По умолчанию

По моему можно рассуждать так:

берем число
x----------------x
Для крайних рахрядов этого числа, как уже было замечено, 9 вариантов

y--------------y
Берем внутреннюю последовательность. Для ее крайних разрядов уже 10 вариантов (добавляется 0). Эти варианты могут быть с любыми цифрами слева и справа (кроме левого нуля). Итого

9 (от предыдущей) + 9*10*10 (если не ошибаюсь).

И так далее для внутренних последовательностей.
alexBlack вне форума Ответить с цитированием
Старый 01.05.2008, 09:32   #3
Иллидан
Форумчанин
 
Регистрация: 16.01.2008
Сообщений: 288
По умолчанию

Хм, а если у числа нечетное число цифр? А если необходимо посчитать от 11 например до 55671?
Иллидан вне форума Ответить с цитированием
Старый 01.05.2008, 10:12   #4
alexBlack
Участник клуба
 
Регистрация: 12.10.2007
Сообщений: 1,204
По умолчанию

Цитата:
Сообщение от Иллидан Посмотреть сообщение
Хм, а если у числа нечетное число цифр?
В конце останется только один
А у этого разряда нет противоположного.

Цитата:
Сообщение от Иллидан Посмотреть сообщение
А если необходимо посчитать от 11 например до 55671?
Здесь нужно подумать, но ИМХО д.б. просто разница между количеством для 55671 и количеством для 11.
alexBlack вне форума Ответить с цитированием
Старый 01.05.2008, 13:15   #5
Иллидан
Форумчанин
 
Регистрация: 16.01.2008
Сообщений: 288
По умолчанию

Цитата:
В конце останется только один
А у этого разряда нет противоположного.
Счиатем от 100 до 999. Получается:
101 111 ... 191. {итого 9}
202 212 ... 292. {итого 9}
...................................
909 919 ... 999. {итого 9}

9*9?

Цитата:
Здесь нужно подумать, но ИМХО д.б. просто разница между количеством для 55671 и количеством для 11.
В каком смысле разница?
Иллидан вне форума Ответить с цитированием
Старый 01.05.2008, 21:02   #6
alexBlack
Участник клуба
 
Регистрация: 12.10.2007
Сообщений: 1,204
По умолчанию

М..да. Вы правы, при попытке реализации все оказалось сложнее чем я предполагал.

Вот функция, которая подсчитывает количество чисел для диапазона
от 00...00 до 99..99 с учетом незначащих нулей.

Z задает количество десятичных знаков.

Код:
function getCountNumber09(Z:integer):integer;
var i, k, k10:integer;
begin
   if Z <= 1     then result := 0
   else if Z = 2 then result := 10
   else if Z = 3 then result := 100
   else begin
      // Просто степень 10^(z-2)
      k10 := 1;
      for i:=1 to Z-2 do begin
         k10 := k10 * 10;
      end;

      k := getCountNumber09(Z-2);
      { Добавляем два разряда слева и справа
        Это значит, что все варианты внутреннего числа
        от 0<00..00>0
        до 0<99..99>0
        повторятся для каждого варианта добавленных разрядов
        Значит повторятся и уже вычисленные числа
      }
      result := k*10*10;
      { Далее добавятся новые варианты
        0 .. 0
        9 .. 9
        Эти варианты будут повторяться k10 раз
      }
      result := result + 10*k10;
      { Добавленные варианты продублируют варианты
        внутреннего числа
      }
      result := result - 10*k;
   end;
end;
getCountNumber09(3) - 100
getCountNumber09(4) - 1900
00000 - 99999 - 19000
000000-999999 - 271000

Думаю, идея понятна. Дальше нужно продумать как это применить для диапазона от
1 до некоторого числа.

А чтобы найти количество в диапазоне можно будет найти количество от 1 до числа b, от 1 до числа a и вычесть из первого второе.

Последний раз редактировалось alexBlack; 02.05.2008 в 00:48.
alexBlack вне форума Ответить с цитированием
Старый 02.05.2008, 10:42   #7
Иллидан
Форумчанин
 
Регистрация: 16.01.2008
Сообщений: 288
По умолчанию

Хм, Как подсчитать от 1 до 9, 99.... до любого кол-во девяток, кажется, понятно. Но, как подсчитать до какого-нибудь 67845 нет очень. Может быть, как-нибудь применить, то что, мы знаем количество от 1 до 99999?
Иллидан вне форума Ответить с цитированием
Старый 02.05.2008, 12:25   #8
alexBlack
Участник клуба
 
Регистрация: 12.10.2007
Сообщений: 1,204
По умолчанию

Цитата:
Сообщение от Иллидан Посмотреть сообщение
Хм, Как подсчитать от 1 до 9, 99.... до любого кол-во девяток, кажется, понятно. Но, как подсчитать до какого-нибудь 67845 нет очень. Может быть, как-нибудь применить, то что, мы знаем количество от 1 до 99999?
Кажется добил. Тест проходит. Правда, код еще нужно дорабатывать - убрать все лишнее, заменить integer на что-то более подходящее для диапазона 10^18...
Вложения
Тип файла: rar test.rar (2.1 Кб, 8 просмотров)

Последний раз редактировалось alexBlack; 02.05.2008 в 17:37.
alexBlack вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
[Pascal]Задача на строки случайных чисел Alyonka_v Помощь студентам 4 28.06.2008 00:58
Задача на строки случайных чисел Alyonka_v Паскаль, Turbo Pascal, PascalABC.NET 2 27.06.2008 21:08
задача:Паскаль и ряд чисел Фибоначчи SEREG@ Помощь студентам 20 16.12.2007 20:05
вычисление суммы чисел, кратных 3 из последовательности, состоящей из 10 чисел, заранее заданных Белка Помощь студентам 3 27.10.2007 11:53
Задача: перевод целых чисел в римские n0x Паскаль, Turbo Pascal, PascalABC.NET 4 12.12.2006 19:52