Алгоритм

← →
Sniffer (2002-05-28 20:40) [0]

Привет всем! Проблема такая, есть число :
31783219310831083108
Можно ли выполнением какого-нибудь алгоритма преобразовать это число в такой вид : xyz, где x, y, z могут быть числами не более чем из трёх знаков, с возможностью получения из xyz исходного числа?

← →
ION T (2002-05-28 21:04) [1]

Шо ты имеешь ввиду под "тремя знаками"? Символы (999:999:999) или байты? В первом случае - никак, а во втором - создаешь саой девятибайтовый тип данных.....

← →
Sniffer (2002-05-28 21:42) [2]

>ION T
Символы(255:255:255). Значит, дело это гиблое?

← →
Anatoly Podgoretsky (2002-05-28 21:57) [3]

Если так, то дело гиблое, то что ты приводишь требует только трез байтов, а у тебя их 9

← →
cypher (2002-05-29 00:15) [4]

Можно наверное... просто у тебя будет не десятичная система исчисления, а.... =))) 999-ричная (сам это выговаривай)...
и обратно тоже просто, стандартный алгоритм первого курса..

← →
Alx2 (2002-05-29 07:44) [5]

Если x, y, z могут быть числами не более чем из трёх знаков (в десятичной системе), то количество возможных значений, получаемых их комбинациями: 1000^3=1000000000 - 10 знаков
А у тебя требуется представить 31783219310831083108 - уже двадцать.
Поэтому с помощью вышеозначенной тройки можно только сетку на более широкий диапазон накинуть. Естественно, очень много чисел ею не накроются, но можно сделать так, чтобы число 31783219310831083108 накрывалось.

А если x,y,z состоят из трех байт, то кол-во вариантов = 256^9= 4722366482869645213696 - тогда твое число элементарно представляется. Вот искомое разложение:
31783219310831083108 = [100, 030, 108] [136, 145, 173] [020, 185, 001]
x = [100, 030, 108]
y = [136, 145, 173]
z = [020, 185, 001]

← →
-=Sergeante=- (2002-05-29 09:27) [6]

2 Alx2© По условию задачи xyz должны состоять из 3-х значных чисел, а не 3-х байтов.

← →
Alx2 (2002-05-29 09:43) [7]

>-=Sergeante=- © (29.05.02 09:27)
>По условию задачи xyz должны состоять из 3-х значных чисел,
>а не 3-х байтов.

Этот случай был рассмотрен в первую очередь:)

Вообще говоря, понятие n-значного числа доопределяется системой счисления. Я же рассмотрел два случая: десятичная система и 256-ричная система.

← →
MBo (2002-05-29 09:44) [8]

в задаче не указано, что такое знак. если это только цифры 0-9, то нельзя, а если в 256-разрядной системе счисления (т.е. каждый символ ASCII - "цифра"), то предложение Alx2 как раз подходит
d#30l ИСн ¶#185#001 (это в кодировке СP866)

← →
Alx2 (2002-05-29 10:01) [9]

Еще добавлю про порядок байтов: чем правее байт, тем больше его адрес, тем он старше.

Если же записать в том порядке, который традиционно (слева-направо) используется при записи чисел (а не так, как они выглядят в дампах памяти) то получится [001, 185, 020] [173, 145, 136] [108, 030, 100]

← →
Sniffer (2002-05-29 15:33) [10]

>Alx2
Спасибо, но я немного не понял....Особенно то место с байтами.
Как вы получили :
x = [100, 030, 108]
y = [136, 145, 173]
z = [020, 185, 001]? Я помню есть какие-то правила перевода, но я их к сожалению не помню. Напомните пожалуйста. Ещё раз всем спасибо.

← →
Alx2 (2002-05-29 15:50) [11]

Раскладываем в 256-ричную систему счисления (а она практически родная для компьютера, посему творится моментально).
Но сначала скажите: как и где вы храните такие большие числа? :)
После ответа на этот вопрос можно продолжить обсуждение.

← →
Sniffer (2002-05-29 16:24) [12]

Такие большие числа хранить можно, ансколько я знаю, только в String. А это связано с некоторыми неудобствами. :(

← →
Alx2 (2002-05-29 16:55) [13]

Со строками, значит... Так называемая длинная арифметика.

А про разложение в нужную систему счисления в двух словах можно сказать так:
Пусть D - основание системы счисления.
N - раскладываемое число.
Тогда очередную цифру разложения получаем так:
1. Находим остаток от деления N на D. p := N mod D - получаем в p очередную цифру разложения.
2. Далее N := N div D и все повторяем снова, пока N>0.

← →
Alx2 (2002-05-29 16:58) [14]

В догонку: получаемые числа разложения идут "задом-наперед" :)
Как находить остаток отделения и целую часть от деления для огромных чисел, записанных в строках - отдельный разговор :)

← →
Sniffer (2002-05-29 17:15) [15]

>Alx2
Сенкс, сча попробую

← →
Sniffer (2002-05-29 18:02) [16]

type
Rslt = record
Number, Ostatok : String
end;
function DecTo(D : integer; N : String) : Rslt;
var
p, i, j : integer;
Need : integer;
begin
Need := StrToInt(Copy(N, 1, Length(IntToStr(D))));
for i := Length(IntToStr(D)) + 1 to (Length(N) - Length(IntToStr(D))) do
begin
p := Need div D;
j := Need - (D * p);
Need := StrToInt(IntToStr(j) + Copy(N, i, 1));
Result.Number := Concat(Result.Number, IntToStr(j))
end;
Result.Ostatok := IntToStr(j);
end;
Посмотрите, где ошибка.

← →
-=Sergeante=- (2002-05-30 10:14) [17]

Вопрос рассмотрен казало бы со всех сторон. Но хотелось бы внести некоторую ясность. Гопода, скажите мне, где Вы последний раз видели числа в 256-ричной системе счисления. Это получается, что в одном разряде(т.е. в 1-м бите) такого числа может поместиться 256 значений! Где жь вы столько цифр с буквами найдёте для представления. Здесь, видимо, имелось ввиду двоичная система счисления с числом разрядов = 8. Т.е. 2^8=256. Т.е. байт.

← →
Alx2 (2002-05-30 10:28) [18]

>-=Sergeante=- © (30.05.02 10:14)

>Где жь вы столько цифр с буквами найдёте для представления
Хм.. про тип char слышали? Диапазон его значений #0..#255 - и каждое из них - символ :)

>Это получается, что в одном разряде(т.е. в 1-м бите)
>такого числа может поместиться 256 значений!
Этак мы и десятичную систему не увидим :) Ведь в одном бите не поместится десять значений?
Вообще говоря, биты сейчас непричем. Мы же не рассматриваем машинное представление чисел?

>Гопода, скажите мне, где Вы последний раз видели числа
>в 256-ричной системе счисления.
Вижу каждый раз, когда просматриваю дампы памяти в отладчике.

>Здесь, видимо, имелось ввиду двоичная система счисления
>с числом разрядов = 8. Т.е. 2^8=256. Т.е. байт.
Двоичная система здесь не рассматривалась.
А то, что 256-ричная и двоичная - близкие родичи - очевидно. И в этом случае из одной в другую числа переводятся просто перегруппировкой разрядов.

← →
Alx2 (2002-05-30 11:39) [19]

>-=Sergeante=- © (30.05.02 10:14)
В догонку, чтобы развеять сомнения.
Классически принято считать, что число N записано в системе счисления с натуральным основанием D>1 и имеет в ней вид
n[0]n[1],...n[m], если сумма n[0]*D^0+n[1]*D^1+..+n[m]*D^m = N. Причем должно выполняться: n[i]<D для любого i=0..m. Сверху это D ничем не ограничено.

D-ричные системы существуют независимо от того, сколько символов в компьютере. Договорились же в 16-ричной системе вместо "10" использовать "A", вместо "11" - "B" и т.д.
А в системе с основанием, например, 2002 можно цифру 1999 законно считать одним знаком и записывать как "1999":)

Алгоритм Найти похожие ветки