| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Работа с текстом(перевёртыш) [D7, XP]
SooM © (2010-05-05 21:43:00)Вводиться число. Совпадает ли оно со своим "перевёртышем"(числом , получающимся при течение данного на оборот).
Заранее спасибо
Омлет (2010-05-07 11:46:00) [21]Еще вариант без опасности переполнения:
function IsNumberPalindrome_om_v2(num: Cardinal; radix: Cardinal = 10): boolean;
var
lpow, rpow: Cardinal;
len, i: Cardinal;
begin;
Result := True;
if num >= radix then
begin
len := Trunc(LogN(radix, num));
lpow := Trunc(IntPower(radix, len));
rpow := 1;
for i := 0 to (len-1) div 2 do
begin
Dec(num, (num div lpow) * (rpow + lpow));
rpow := rpow * radix;
if (num mod rpow) <> 0 then
begin
Result := False;
Break;
end;
lpow := lpow div radix;
end;
end;
end;
Сложных операций больше, но цикл половинный и на не палиндромах досрочно завершается.
Sha (2010-05-07 08:44:00) [22]Версия алгоритма [39] с дополнительной проверкой переполнения работает верно (как и алгоритм [34]):
function CorrectedIsNumberPalindrome(num: cardinal; radix: cardinal= 10): boolean;
const
MaxCardinal= cardinal(-1);
var
save, cpy, rev, prev: cardinal;
begin;
if num<radix
then Result:=true
else begin;
save:=num;
rev:=0;
repeat;
cpy:=num;
num:=num div radix;
prev:=rev;
rev:=(rev-num) * radix + cpy;
until num=0;
Result:=(rev=save) and (prev<=(MaxCardinal-cpy) div radix);
end;
end;
Она требует меньше умножений/делений, чем алгоритмы [27] и [41]
но больше, чем алгоритм [34].
Sha (2010-05-06 23:43:00) [23]Дико извиняюсь, не то скопапистил. Версия алгоритма [27] для cardinal выглядит так
//Из-за переполнения может выдавать неверный положительный результат
function Alg27IsNumberPalindrome(num: cardinal; radix: cardinal= 10): boolean;
var
save, rev: cardinal;
begin;
if num<radix
then Result:=true
else begin;
save:=num;
rev:=0;
repeat;
rev:=rev * radix + num mod radix;
num:=num div radix;
until (num=0);
Result:=(rev=save);
end;
end;
и выдает те же неверные результаты, что и [39]
Sha (2010-05-06 23:19:00) [24]Версия алгоритма [27] для cardinal также работает не всегда верно:
//Неверно работает для radix=1025, num=2149584896(10) 1.1021.5.1021(1025)
function Alg27IsNumberPalindrome(num: cardinal; radix: cardinal= 10): boolean;
var
save, rev: cardinal;
begin;
if num<radix
then Result:=true
else begin;
save:=num;
rev:=0;
repeat;
rev:=rev * radix + num mod radix;
num:=num div radix;
until (num=0);
Result:=(num=rev);
end;
end;
Sha (2010-05-06 22:36:00) [25]Обнаружено, что алгоритм
//Из-за переполнения может выдавать неверный положительный результат
function StdIsNumberPalindrome(num: cardinal; radix: cardinal= 10): boolean;
var
save, cpy, rev: cardinal;
begin;
if num<radix
then Result:=true
else begin;
save:=num;
rev:=0;
repeat;
cpy:=num;
num:=num div radix;
rev:=(rev-num) * radix + cpy;
until num=0;
Result:=(rev=save);
end;
end;
более чем в 128000 случаях выдает неверный результат для radix=1025, например, для таких чисел
1 1089498130(10) 1.12.0.5(1025)
2 1090549780(10) 1.13.1.5(1025)
3 1091601430(10) 1.14.2.5(1025)
4 1092653080(10) 1.15.3.5(1025)
5 1093704730(10) 1.16.4.5(1025)
6 1094756380(10) 1.17.5.5(1025)
7 1095808030(10) 1.18.6.5(1025)
8 1096859680(10) 1.19.7.5(1025)
9 1097911330(10) 1.20.8.5(1025)
Sha (2010-05-06 17:42:00) [26]В работе алгоритма, аналогичного [27], с параметром integer
не удалось обнаружить ошибок, вызванных переполнением,
для всех значений radix в диапазоне 2..13 и нечетных значений 15,17,19...35.
Омлет (2010-05-06 16:04:00) [27]> Омлет © (06.05.10 15:50) [35]
> компилятор не ругается
Вру. Ругается. Просто я варнинг не заметил.
Омлет (2010-05-06 15:56:00) [28]> Если параметр объявить как cardinal, получим правильный
> ответ для cardinal.
И надо не забыть{$Q-}
Омлет (2010-05-06 15:50:00) [29]Да, так работает.
> Это не integer, a cardinal, так что все верно.
Проблема в том, что компилятор не ругается на выход за пределы диапазона. А на глаз сразу и не скажешь, что это число уже не Integer ))
Sha (2010-05-06 15:38:00) [30]> ShaIsNumberPalindrome(11) = False
Да, это ошибка.
Вынес первую итерацию из цикла, а repeat на while заменить забыл.
Хотелось поскорее найти переполнения.
Надеюсь, так будет верно
function ShaIsNumberPalindrome(num: integer; radix: integer= 10): boolean;
var
cpy, rev: integer;
begin;
if num<radix
then Result:=(num>=0)
else begin;
cpy:=num;
num:=num div radix;
rev:=cpy - num * radix;
if rev=0
then Result:=false
else begin;
while (rev<>num) and (rev<cpy) do begin;
cpy:=num;
num:=num div radix;
rev:=radix * (rev-num) + cpy;
end;
Result:=(rev<=cpy);
end;
end;
end;
> ShaIsNumberPalindrome(3999999993) = False
Это не integer, a cardinal, так что все верно.
Если параметр объявить как cardinal, получим правильный ответ для cardinal.
Омлет (2010-05-06 15:26:00) [31]И еще - подлянка от Дельфи:
ShaIsNumberPalindrome(3999999993) = False
Омлет (2010-05-06 15:16:00) [32]> Sha © (06.05.10 15:09) [31]
ShaIsNumberPalindrome(11) = False
Sha (2010-05-06 15:09:00) [33]Исправленная версия алгоритма [24]
function ShaIsNumberPalindrome(num: integer; radix: integer= 10): boolean;
var
cpy, rev: integer;
begin;
if num<radix
then Result:=(num>=0)
else begin;
cpy:=num;
num:=num div radix;
rev:=cpy - num * radix;
if rev=0
then Result:=false
else begin;
repeat;
cpy:=num;
num:=num div radix;
rev:=radix * (rev-num) + cpy;
until (rev>=cpy) or (rev=num);
Result:=(rev<=cpy);
end;
end;
end;
Sha (2010-05-06 14:55:00) [34]> Если только для целочисленных типов из Delphi.
Именно это я имел в виду.
DVM (2010-05-06 14:53:00) [35]
> Sha © (06.05.10 13:07) [28]
> Интересно было бы продемонстрировать это на примере для
> произвольного основания системы счисления и разрядности
> чисел.
Для произвольной разрядности надо знать представление числа в памяти. Универсальный алгоритм вряд ли возможен. Если только для целочисленных типов из Delphi.
Sha (2010-05-06 13:07:00) [36]Алгоритм [24] может выдать неверный положительный результат, если число оканчивается нулем, например, 10.
Алгоритмы, основанные на 'перевороте' числа и сравнении с исходным числом
теоретически тоже могут выдать неверный положительный результат
из-за возможного переполнения.
Интересно было бы продемонстрировать это на примере для произвольного основания системы счисления и разрядности чисел.
Омлет (2010-05-06 12:08:00) [37]
function IsPalindrome(N: Integer): Boolean;
var
X, Y: Integer;
begin
if N < 10 then
Result := (N >= 0)
else begin
X := 0;
Y := N;
repeat
X := X * 10 + Y mod 10;
Y := Y div 10;
until (Y = 0);
Result := (N = X);
end;
end;
Anatoly Podgoretsky (2010-05-06 07:26:00) [38]> Игорь Шевченко (05.05.2010 23:53:22) [22]
Тебе попалась методичка, все вопросы из который взяты с delphimaster
Германн (2010-05-06 02:21:00) [39]
> DVM © (05.05.10 23:51) [21]
>
>
> > Inovet ©
>
> что характерно, прошел год ровно.
>
Ну и опять ученики кулинарного техникума получили задание из той же самой методички.
Sha (2010-05-06 01:39:00) [40]
function IsNumberPalindrome(num: integer): boolean;
var
cpy, pal: integer;
begin;
if (num<0) or (num>2147447412) //MaxInt=2147483647
then Result:=false
else begin;
pal:=0;
repeat;
cpy:=num;
num:=num div 10;
pal:=10*(pal-num) + cpy;
until (pal>=cpy) or (pal=num);
Result:=(pal<=cpy);
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
const
Answers: array[boolean] of string= ('нет', 'да');
begin;
Edit2.Text:=Answers[IsNumberPalindrome(StrToIntDef(Edit1.Text,-1))];
end;
| |
Страницы: 