Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Как одном числе хранить сумму трех чисел


Автор: Delphist 17.3.2008, 20:14
1. Стала такая задача, есть три числа a, b, c в сумме они дают 100, a + b + c = 100; 
Нужно суммы этих чисел представить через какую-то функцию кодирования (или другим способом) в число, чтобы 
потом по этому числу применяя функции декодирования можно было получить эти три числа, т.е. 
SomeMathFuncCode(a, b, c) = d;
SomeMathFuncDecode(d) = {a, b, c}

2. Как это же реализовать если, чисел > 3 т.е (a, b, c, d, ...) и сумма их равна не 100, а заданному числу X.

Примечание: a, b, c - могут быть дробными

Автор: Sardar 17.3.2008, 20:43
Пусть число ограничено 8 битами, тогда побитовым сдвигом влево все три числа и берём сумму (ну или OR побитовое если числа могут быть негативными). Обратно AND побитовое по маске, сдвиг обратно в право. В обычный uint(32) уложиться 4 таких числа, для других размерностей принцип тот же.

Восстановить сумму из трёх произвольных по значению и размерам числа по моему не возможно.

Автор: Delphist 17.3.2008, 20:46
Цитата(Sardar @  17.3.2008,  21:43 Найти цитируемый пост)
Пусть число ограничено 8 битами, тогда побитовым сдвигом влево все три числа и берём сумму (ну или OR побитовое если числа могут быть негативными). Обратно AND побитовое по маске, сдвиг обратно в право. В обычный uint(32) уложиться 4 таких числа, для других размерностей принцип тот же.

Мог бы этот алгоритмик как-нить программно зарисовать, а то не совсем понятно.

Автор: 4d5a 17.3.2008, 21:03
А почему бы не так

Код


function encode(a,b,c:integer):integer;
begin
  result:=(a shl 16) or (b shl 8) or c;
end;
procedure decode(d:integer; var a,b,c:integer);
var bt:integer;
begin
  bt:=$ff;                  
  c:=d and bt; bt:= bt shl 8;
  b:=(d and bt)shr 8; bt:=bt shl 8;
  a:=(d and bt)shr 16;
end;



Цитата(Delphist @  17.3.2008,  20:14 Найти цитируемый пост)
2. Как это же реализовать если, чисел > 3 т.е (a, b, c, d, ...) и сумма их равна не 100, а заданному числу X.


Тогда надо еще доказать что при выбранном методе 'уплотнения' они влезут в это число smile 

Автор: Akina 17.3.2008, 21:12
Исходная задача - это типичная задача хранения избыточных данных.
Самое простое - это хранение минимально необходимых данных, которые позволяют восстановить недостающие.
Например в исходном случае, если надо хранить ровно 3 числа (a,b,c), их сумма всегда равна 100 и они всегда неотрицательны, достаточно хранить одно число N = 100*a+b. Очевидно, что этого числа достаточно, чтобы восстановить всю тройку (a=N\100; b=N%100; c=100-a-b).
Для любого другого варианта просто необходимо определить, какие данные являются избыточными, выбросить их, а из оставшихся составить выражение с однозначным соответствием.

Автор: VICTAR 17.3.2008, 21:17
Уже ответили... Ну не зря же я старался  smile 
Код

type 
Bytes= array [0..3] of Byte;

function ToBytes(const Source: Cardinal): Bytes;
var
  i: Byte;
begin
  for i := 0 to 3 do
    Result[i] := Source shr (8 * i) and $000000FF;
end;

function ToInt(const Source: Bytes): Cardinal;
var
  i: Byte;
begin
  Result := 0;
  for i := 0 to 3 do
    Inc(Result, Source[i] shl (8 * i));
end;

Автор: sergejzr 17.3.2008, 23:08
Akina, как всегда - максимус элегантус!  smile 

Автор: Delphist 18.3.2008, 09:56
Цитата(Akina @  17.3.2008,  22:12 Найти цитируемый пост)
Самое простое - это хранение минимально необходимых данных, которые позволяют восстановить недостающие.
Например в исходном случае, если надо хранить ровно 3 числа (a,b,c), их сумма всегда равна 100 и они всегда неотрицательны, достаточно хранить одно число N = 100*a+b.

Твой метод не работает, если числа дробные. А мне нужен как раз для дробных чисел

Автор: Akina 18.3.2008, 10:02
Цитата(Delphist @  18.3.2008,  10:56 Найти цитируемый пост)
метод не работает, если числа дробные. А мне нужен как раз для дробных чисел

А я не телепат. Хочешь получить решение для задачи, озвучив только треть условий? 
Впрочем, ПРИНЦИП от этого не меняется.

Автор: ama_kid 18.3.2008, 10:08
Цитата(Delphist @  18.3.2008,  09:56 Найти цитируемый пост)
А мне нужен как раз для дробных чисел
Как вариант - можно рассмотреть случай с ограничением числа знаков после запятой: к примеру у тебя есть числа 21.29, 41.35 и 37.36. В сумме они дают требуемую сотню. Тогда переводим числа из дробного вида в целый путем умножения на 100: 2129+4135+3736 = 10000. Дальше все сводится к методу, описанному Akina... 

Автор: Delphist 18.3.2008, 10:23
Цитата(ama_kid @  18.3.2008,  11:08 Найти цитируемый пост)
 Дальше все сводится к методу, описанному Akina...  

Неа не сводится, метод Akina работает с целыми числами (a, b, c) непревышающие 255

Автор: ama_kid 18.3.2008, 11:01
Цитата(Delphist @  18.3.2008,  10:23 Найти цитируемый пост)
Неа не сводится, метод Akina работает с целыми числами (a, b, c) непревышающие 255 
Сводится, только размер хранимого числа требованием "для дробных чисел" увеличивается с байта до Integer:
N=10000*a+b = 10000*2129+4135=21294135
Восстанавливаем числа:
a = N\10000 = 2129 (затем превращаем в дробное делением на 100) = 21.29
b = N%10000 = 4135 =>41.35
c = 100.00 - a - b => 37.36
P.S. Все это рассматриваю как пример, не больше. В конечном итоге надо исходить из конкретных данных, вполне возможно ограничение числа знаков после запятой некорректно...

Автор: Akina 18.3.2008, 13:41
Цитата(Delphist @  18.3.2008,  11:23 Найти цитируемый пост)
Неа не сводится, метод Akina работает с целыми числами (a, b, c) непревышающие 255 

Позволю себе процитировать себя же
Цитата(Akina @  17.3.2008,  22:12 Найти цитируемый пост)
составить выражение с однозначным соответствием

Автор: Delphist 18.3.2008, 20:18
Цитата(Akina @  18.3.2008,  14:41 Найти цитируемый пост)
составить выражение с однозначным соответствием

Не понял

Автор: sergejzr 18.3.2008, 21:29
Цитата(Delphist @  18.3.2008,  09:23 Найти цитируемый пост)
Неа не сводится, метод Akina работает с целыми числами (a, b, c) непревышающие 255 

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

Автор: Akina 18.3.2008, 21:40
Цитата(Delphist @  18.3.2008,  21:18 Найти цитируемый пост)
Не понял 

Да это тебя пока никто не понял. Ты до сих пор не сформулировал задачу ПОЛНОСТЬЮ. Со всеми условиями, в ти.ч. граничными. А мы, как дураки, гадаем на кофейной гуще, что же у тебя там собсно происходит и с чем именно. Я, например, до сих пор не знаю, какими могут быть эти а-бэ-цэ - только положительными или еще и нулевыми и даже отрицательными, простой они точности или двойной, или точность задана...
Неужели трудно точно поставить задачу?

Автор: Delphist 19.3.2008, 15:19
Цитата(Akina @  18.3.2008,  22:40 Найти цитируемый пост)
Неужели трудно точно поставить задачу? 

числа a, b, c могут быть дробными, функции EnCode превращает их в одно число d (целое или дробное), а функция DeCode превращает из числа d их обратно в три числа a, b, c

Вот собственно и все

Автор: mes 19.3.2008, 15:42
Цитата(Delphist @  19.3.2008,  15:19 Найти цитируемый пост)
числа a, b, c могут быть

лучше тогда вопрос: а какими они не могут быть? 

так как вышеописанное условие не соответствует фразе
Цитата(Akina @  18.3.2008,  21:40 Найти цитируемый пост)
 Со всеми условиями, в ти.ч. граничными

Автор: Akina 19.3.2008, 15:50
Цитата(Delphist @  19.3.2008,  16:19 Найти цитируемый пост)
числа a, b, c могут быть дробными

Извини за грубость, но термин "дробные" надо было забыть еще в детском саду. Real? Double? или какие там у вас в Дельфах есть типы... ограничения на значения есть? какие именно?

Автор: 4d5a 20.3.2008, 20:52
Думаю из всего вышесказанного можно наконец то выпарить точную формулировку задачи:

Даны три рациональных числа (a,b,c), представленных в виде десятичной дроби. 
Каждое число принадлежит промежутку [0;100]. Максимальное количество знаков(десятичных) после запятой равно X0. Для ввода и вывода чисел используется тип double: 8 byte.
Найти функцию FY(Y1,Y2,Y3)->{Y0}, и обратную ей функцию FZ(Z0)->{Z1,Z2,Z3} которые удовлетворяют условию
FY(FZ(V))=V 
(запись "->{Z1,Z2,Z3}" означает что функция возвращает три значения)
Причем, ф-ия FY ставит в соответсвие одной тройке аргументов Y1,Y2,Y3 одно значение Y0,
а ф-ия FZ сопоставляет одному значению Z0 одну уникальную комбинацию Z1,Z2,Z3. Т.е. имеет место однозначное соответствие.
Реализовать FY,FZ двумя процедурами на унивесальном ЯП или в словестном виде.

К примеру, X0=2

Замечание: изначально предпологается что в 8 байтах хватит места для a,b,c. За это предположение отвечает условие X0=2

Delphist, поправте если не так

Автор: 4d5a 20.3.2008, 21:27
но если я правильно понял задачу, Вам уже дали общий метод ее решения (см. далее). В чем вопрос - то еще ????????

Цитата(Akina @  17.3.2008,  21:12 Найти цитируемый пост)
 необходимо определить, какие данные являются избыточными, выбросить их, а из оставшихся составить выражение с однозначным соответствием



Цитата(ama_kid @  18.3.2008,  11:01 Найти цитируемый пост)
N=10000*a+b = 10000*2129+4135=21294135Восстанавливаем числа:a = N\10000 = 2129 (затем превращаем в дробное делением на 100) = 21.29b = N%10000 = 4135 =>41.35c = 100.00 - a - b => 37.36

Автор: Delphist 21.3.2008, 09:51
Цитата(4d5a @  20.3.2008,  21:52 Найти цитируемый пост)
амечание: изначально предпологается что в 8 байтах хватит места для a,b,c. За это предположение отвечает условие X0=2

Все правильно, но X0 может меняться от 1 до 5

Автор: Akina 21.3.2008, 10:19
Цитата(Delphist @  21.3.2008,  10:51 Найти цитируемый пост)
X0 может меняться от 1 до 5 

Значит X0 = 5. Итого требуется хранение числа, состоящего из максимум 7 цифр. Следовательно:

(long*64) Hash = 2**32 * (long*32) (a * 10**5) + (long*32) (b * 10**5)

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)