Пятничная задачка

← →
MBo © (2009-09-11 08:45) [0]

Васе Пупкину нужно написать функцию, которая возвращает количество числовых палиндромов от 1 до заданного натурального числа включительно. Число называется палиндромом, если его десятичная запись читается одинаково слева направо и справа налево, например, 53235.
прототип
function PalindromeCount(const N:Int64): Int64;
например, для N = 101 результат - 19 (1..9, 11, 22..99, 101)
Как Васе сделать это наиболее эффективно?

← →
Sergey Masloff (2009-09-11 09:59) [1]

Смотря что понимать под эффективностью ;-)
Если минимальные затраты дорогостоящего труда программиста то можно тупо переворачивать строковое представление и сравнивать на равенство.

Я сам помнится будучи васей пупкиным решал это задание на 1 курсе института (строки перворачивать было нельзя)

← →
Дмитрий С © (2009-09-11 10:02) [2]

> Sergey Masloff (11.09.09 09:59) [1]

Ну можно и палиндромы перебрать по формулам типа:
a
a+10b
a+10b+100a
...
И посчитать их количество до заданного.
Интересно, математически наверняка можно решить :)

← →
Павел Калугин © (2009-09-11 10:02) [3]

> [1] Sergey Masloff (11.09.09 09:59)
> (строки перворачивать было нельзя)

Сравнивали разряды в первой и последней позиции, второй и предпоследней и так далее?

← →
Павел Калугин © (2009-09-11 10:03) [4]

> [2] Дмитрий С © (11.09.09 10:02)
> a
> a+10b
> a+10b+100a

тогда уж
a+10a

← →
Чесслово (2009-09-11 10:20) [5]

>Васе Пупкину нужно написать функцию...
>Как Васе сделать это наиболее эффективно?
Спросить на форуме

← →
Alx2 © (2009-09-11 10:29) [6]

Гады... У меня работы полно, а тут - задачка. :)

← →
Дуб © (2009-09-11 10:34) [7]

> Alx2 © (11.09.09 10:29) [6]

Для 10 в степени - ответ выписывается сразу. А вот для тех, что от ближайшей степени до числа - уже интереснее.

← →
Alx2 © (2009-09-11 10:45) [8]

> Дуб © (11.09.09 10:34) [7]

Я пока навскидку смотрю как на количество целочисленных точек, которые сидят на "палиндромной" плоскости, соответствующим образом ограниченной. Т.е. как на кол-во решений некоторого диофантова уравнения. Оно обычно быстро может быть подсчитано. Но серьезно туда думать - никак :)

← →
Дуб © (2009-09-11 11:30) [9]

> Alx2 © (11.09.09 10:45) [8]

При дамах попрошу не выражаться. У меня вышло довольно просто все.

← →
Alx2 © (2009-09-11 11:59) [10]

>Дуб © (11.09.09 11:30) [9]

Хм... да, ты прав. Я загнался. Нашел как сделать значительно проще.

← →
Дмитрий С © (2009-09-11 13:06) [11]

Идеи то какие?
У меня идея такая:
1. Находим по формуле количество палиндромов для ближайшей степени двойки:
Например, для числа 5"345"232 это будет 1"000"000
2. Прибавляем к нему число оставшихся палиндромов, путем отбрасывания половины знаков:
Например, для 5"345"232 нужно прибавить: 5"345
3. Компенсировать неточность предыдущего этапа.

← →
Дуб © (2009-09-11 13:11) [12]

> 1. Находим по формуле количество палиндромов для ближайшей
> степени двойки:

десятки

> 2. Прибавляем к нему число оставшихся палиндромов, путем
> отбрасывания половины знаков:

Для четного числа знаков так. Для нечетного чуть сложнее.

> 3. Компенсировать неточность предыдущего этапа.

так, да.

← →
Дмитрий С © (2009-09-11 13:12) [13]

В первом пункте обозначена ближайшая степень двойки, а число палиндромов находится по формуле: S(X).
function O(X: Int64): Int64; inline; begin Result := Round(Power(10, (X+1) div 2) - 1) div 9; end; function S(X: Int64): Int64; inline; begin Result := 18*(O(X) - (X mod 2)*5*Round(Power(10, X div 2 - 1))); end;

← →
Дмитрий С © (2009-09-11 13:13) [14]

десятки, точно.

← →
Дуб © (2009-09-11 13:13) [15]

> Для четного числа знаков так. Для нечетного чуть сложнее

и отнять надо еще, степень десятки.

← →
Дмитрий С © (2009-09-11 13:16) [16]

Блин, забыл уточнить.
S(X), тут X - это количество знаков в числе

← →
MBo © (2009-09-11 15:07) [17]

>Дмитрий С © (11.09.09 13:12) [13]
что-то я запутался в X-ах, где что обозначает

← →
Омлет (2009-09-11 15:19) [18]

Для степеней десятки можно ускорить :)

const
Power10_PaliCount: array [1..18] of Integer =
(9,18,108,198,1098,1998,10998,19998,109998,199998,1099998,1999998,10999998,
19999998,109999998,199999998,1099999998,1999999998);

if N > 9 then
begin
Len := Ceil(Log10(N + 1)); // Число разрядов
Result := Power10_PaliCount[Len-1];
end

Дальше сложнее.. Надо рекурсивно что ли разряды уменьшать..

← →
Омлет (2009-09-11 15:32) [19]

Или рекурсивно спускаться, уменьшая порядок числа, прибавляя по 9*(10^X), где X = Len div 2.
Но нужно еще как-то при этом учитывать остаток.

← →
oldman © (2009-09-11 17:11) [20]

> Васе Пупкину нужно написать функцию, которая возвращает
> количество числовых палиндромов от 1 до заданного натурального
> числа включительно.

Например, в заданном числе N разрядов.
Числа a в виде "сс" (где с меняется от 1 до b=половина разрядов N), будут палиндромами

Например, N=16 (2 разряда)
b должно иметь один разряд (от 1 до 9)
Палиндромы для a от 1 до 9:
11
(22>N)

Надеюсь, идея понятна... (Васе пупкину не забыть про нечетное количество разрядов!!!)

Для N=1234 палиндромы:
1
2
3
4
5
6
7
8
9
11
22
33
44
55
66
77
88
99
111
121
131
...
999
1001
1111
1221

← →
Дуб © (2009-09-11 17:24) [21]

> MBo © (11.09.09 15:07) [17]

Там сложно. Но ты именно то, что в итоге описано подразумевал?

Или за пазухой бомбу держишь?

← →
MBo © (2009-09-11 20:06) [22]

>Но ты именно то, что в итоге описано подразумевал?

Ну я мог и ничего не подразумевать, а просто любопытствовать ;)

[13] мне непонятно, а подход [11] - понятен. Однако дьявол может скрываться в деталях- это насчет компенсации неточностей.

> MBo © (11.09.09 20:06) [22]

Ну да, пункт 3 очень широк. :)

Я на тройке примеров распишу как считается:

1. 5345236 F = 6343

F = 999 + 999 + (534-100)*10 + 6 -1

2. 5345532 F = 6344

F = 999 + 999 + (534-100)*10 + 6

3. 534527 F = 1533

F = 999 + 99 + 535-100

3. 534227 F = 1532

F = 999 + 99 + 535-100 -1

← →
Омлет (2009-09-13 21:24) [24]

Примерное решение
http://mathworld.wolfram.com/PalindromicNumber.html

← →
Achpile (2009-09-14 14:47) [25]

Надо заметить, что для любого четного числа разрядов кол-во полиномов равно кол-ву полиномов для предшествующего нечетного...

f(1) = 9
f(2) = 9
f(3) = 9 * 10
f(4) = 9 * 10
f(5) = 9 * 10 * 10 и т.д.

т.е.

f(x) = 9 * 10^((x - 1) div 2)

N"грубое" = E(i = 1 to n-1) f(i)

N"грубое" - число полиномов без учета сравнения с заданным
E - сумма
n - число разрядов заданного числа

Далее изучаем цифры в разрядах:

первая цифра a, для нее полиномов существует (a-1)*f(n-2)
вторая цифра b, для нее прибавляем (b-1)*f(n-4)

и так продолжаем до (n div 2) разряда.

← →
Achpile (2009-09-14 14:48) [26]

и еще + 1 для числа 0

← →
SP (2009-09-14 17:41) [27]

Хм... Все бы получалось довольно просто, типа так:

function PalindromeCount(const N:Int64): Int64; var l,i:integer; t,v:int64; begin l:=trunc(Log10(N))+1; result:=0; t:=1; v:=1; for i:=1 to l-1 do begin result:=result+t*9; if odd(i) then v:=v*10 else t:=t*10; end; result:=result+(N div t)-v+1; end;

вот только проблема с определением не является ли последнее число палиндромом, поэтому указанная ф-ция не всегда правильно работает.
например для числа 1000 кол-во палиндромов должно быть на 1 меньше чем для числа 1001
Но не могу пока для этого написать компактный код

← →
SP (2009-09-14 18:32) [28]

ну можно так написать:
function PalindromeCount(const N:Int64): Int64; var l,i:integer; t,v:int64; a,b,k:integer; p,q,y:int64; begin l:=trunc(Log10(N))+1; result:=0; t:=1; v:=1; for i:=1 to l-1 do begin result:=result+t*9; if odd(i) then v:=v*10 else t:=t*10; end; y:=t*v; k:=1; p:=N; q:=N; for i:=1 to trunc(l/2) do begin a:=p mod 10; p:=p div 10; b:=q div y; q:=q mod y; y:=y div 10; if a>b then k:=1; if a<b then k:=0 end; result:=result+(N div t)-v+k; end;

только как-то не совсем красиво получается...

очень коротко и красиво, наверно, не получится.

← →
SP (2009-09-14 18:58) [30]

Ну для приведения в немного более компактный вид можно убрать некоторые переменные и использовать вместо них старые, которые уже не нужны...
Но это мало сократит код.

← →
SP (2009-09-14 21:04) [31]

> for i:=1 to trunc(l/2) do

м-да. глупость написал...

Лучше так
... for i:=1 to l shr 1 do ...

Пятничная задачка Найти похожие ветки