Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Microsoft Access [игнор отключен] [закрыт для гостей] / распределение суммы на несколько частей с точностью до целого / 19 сообщений из 19, страница 1 из 1
18.09.2003, 09:25
    #32268656
АлексейК
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
есть задача: распределение некоторой целой суммы на несколько частей с точностью до целой части. причем сумма получившихся частей должна быть равна начальной сумме. Все хорошо когда все делится на целое число , но когда остаток ...

я принял следующую методику

Код: plaintext
1.
2.
3.
 1  делю на части с округлением
 2  считаю сумму получившегося
 3  считаю разницу между исходным значением и суммой частей - получаю +/- остаток
 4  +/- остаток отношу к самой большой части 


есть ли математические способы решения данной задачи ?
...
Рейтинг: 0 / 0
18.09.2003, 17:01
    #32269504
Владимир Саныч
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
Когда я изучал геодезию, там алгоритм был почти такой же. Только пункт 4 выглядел иначе: раскидывали по 1 по всем частям, начиная с самой большой.

Только там пункта 1 не было. Если просто делить, то части будут одинаковые, самой большой части не будет.

Пример: 7+8+11=26, а надо 28. Значит, добавляем по 1 к 11 и к 8.
...
Рейтинг: 0 / 0
18.09.2003, 18:21
    #32269594
assa
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
можете раскидать и _"дробь"_ /а не _целое_/. А разницу между входящим и остатком отнести на наибольшее. ТщательнеЕ получится.

Это, как я понимаю, "раскидывание " ошибок округления по НДС - ам и т.п.?
...
Рейтинг: 0 / 0
18.09.2003, 18:40
    #32269613
распределение суммы на несколько частей с точностью до целого
Sub DelInt()
Dim a&, b&, c&, d&
a = 20
b = a \ 3
c = (a - b) \ 2
d = a - b - c
MsgBox b & " " & c & " " & d
End Sub

Получаем: 6 7 7
...
Рейтинг: 0 / 0
18.09.2003, 19:00
    #32269632
АлексейК
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
спасибо, кончно ...

но я в душе надеялся что мало ли есть в форуме - гений - математик который предложил бы решение в одну строку - математической формулой

способ саныча достаточно интересный но в моем случае не подойдет так как в большинстве случаев у меня одна часть более 70% а остальные маленькие и если от остатка остается 2 единицы то разумнее отнести на самую крупную сумму

а вот способ assa я чего -то не совсем понял.

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

пример
для достижения нужной суммы скоректировать набор из 4 чисел вверх на + 1 единицу


10.1 -> 11 то погрешность составит 0.9/10.1 = 0,0891089 ....
9.4 -> 10 то погрешность составит 0.6/9.4 =0,0638297.....
3.3 -> 4 то погрешность составит 0.7/3.3 =0,2121212.....
2.9 -> 3 то погрешность составит 0.1/2.9 =0,0344827.....

отсюда видно что увеличивать надо 2.9 а если еще единица то 9.4
...
Рейтинг: 0 / 0
18.09.2003, 19:41
    #32269662
assa
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
А что не понятно? Я ж не читал задачку: )
А понял: "раскидать сумму по частям".
_____________

Поразмышляем о целочисленной математике:

есть величина A (целая). Делится между емкостями b,c,d,... x по некоему закону. Емкости целочисленные. Куда девать остаток?

Ответ1. Распределить в пропорции.

Наводящий вопрос: пропорция дает дроби. Что делать?

Ответ2. дроби округлить (математически). Разницу между исходным и суммой результатов отнести на наиболшие члены.


Вопрос 2. Как относить разницу?
допустим что-то типа:
dlt=(a-b-c-d-..x)
db=round(dlt*a/b)
dlt = dlt-db
dc=round(dlt*a/c)
...

но проблема в том, что b~c~d~...x приводит к тому, что уже db=0 (т.е. число слагаемых больше 2*остаток). тогда остаток надо раскидывать на старшие члены.

Как? И на какие?

если остаток =n, то берем ИМЕННО n старших членов (емкостей), и составляем пропорцию. Тогда уж точно, dx(i) в большей части будут >0.5.

а остаток будет несложно раскидать на следующие, за "получившими" надбавку.
______
Резюме:
1. Раскидываем (но не целочисленно, а нормальным делением с последующим округлением!).
2. Высчитываем разницу (между дробью и округленной величиной) и по ней (ее величине) ранжируем
3. Разницу N раскидываем по N старшим _разницам_ ("ошибкам округления") в том же порядке.
2. (опять) Высчитываем разницу между "идеальными [дробными - расчетными "нормальным делением"] величинами" и текущими, и по ней (ее величине) ранжируем.
3. повторяем 3. с новым n и новыми "ошибками" и их ранжиром.

где-то так :0).

_____
ЗЫ: Можно пользоваться целочисленным делением, но и при разнесении остатков пользоваться не обычным "старшинством" по величине, а сравнением остатков от целочисленного деления. (а вот чего и на что - надо покумекать, но в лом-с - пьян-с).
...
Рейтинг: 0 / 0
18.09.2003, 19:51
    #32269668
вадя
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
если assa прав...
то есть такое понятие как НДС внутри, и НДС сверху .
может использовать это?
у меня есть такая параметра на форме . для каждого клиента можно сделать накладную либо - цена целое, цена с ндс как получится
либо цена с ндс целое, цена -как получится.
...
Рейтинг: 0 / 0
19.09.2003, 09:13
    #32269846
Май (хо-о-о-рошенькая!!!)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
Владимир Саныч
А чё такэ "Когда я изучал геодезию... ". Новое слово какое-то... "Гео" - понятно, что-то земное, а вот "-де" (de чего?)?!
...
Рейтинг: 0 / 0
19.09.2003, 09:20
    #32269854
Alexander G
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
Класс!!!
Новое слово!
В словарь загляни.
...
Рейтинг: 0 / 0
19.09.2003, 09:26
    #32269858
АлексейК
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
некоторая степень "простоты" украшает девушку. написано ведь. хорошенькая. не будем строги.
...
Рейтинг: 0 / 0
19.09.2003, 09:30
    #32269862
sasha_1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
>нужно что-то логическое - такое чтоб давало минимальную погрешность

так а если использовать твой же алгоритм
>1 делю на части с округлением
>2 считаю сумму получившегося
>3 считаю разницу между исходным значением и суммой частей - получаю +/-
>остаток
>4 +/- остаток отношу к самой большой части

только 1 и 4 пункт заменить на
1_new. делю на части с отсечением
4_new. + остаток отношу к части у которой максимально отношение дробной части к целой.

имхо, это и будет минимальная погрешность.
...
Рейтинг: 0 / 0
19.09.2003, 09:38
    #32269868
АлексейК
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
2 sasa

только нужно еще будет добавить учет погрешности для каждой записи и пересчет ее с добавлением каждой единицы - так как бывает нужно +/-1 или +/-2 итд. для достижения правильной суммы.
...
Рейтинг: 0 / 0
19.09.2003, 09:47
    #32269882
Valer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
в математике это называется задача рюкзака
пример
емкость =100
есть предметы
объемом 34, 32, 29 ,,, 3
в рюкзак надо засунуть мах объем ( вес)
самый простой алгоритм
предметы отсортированы по объему
while
пытаемся положить в рюкзак самый большой предмет
который может влезть
проверяем оставшийся объем
loop

Алексей оставшуюся часть может разнести к любому предмету

для числа предметов 10-20 можно пробовать полный перебор вариантов
на большой размерности резко возрастает число вариантов
задача NP полная
...
Рейтинг: 0 / 0
19.09.2003, 09:49
    #32269885
Polev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
в математике это называется задача рюкзака
пример
емкость =100
есть предметы
объемом 34, 32, 29 ,,, 3
в рюкзак надо засунуть мах объем ( вес)
самый простой алгоритм
предметы отсортированы по объему
while
пытаемся положить в рюкзак самый большой предмет
который может влезть
проверяем оставшийся объем
loop

Я так понял не самый лучший алгоритм :)
Скажем предметы объемом 75, 33, 33, 33....
...
Рейтинг: 0 / 0
19.09.2003, 10:10
    #32269907
Valer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
лучшим алгоритмом может быть только
полный перебор вариантов
для 100 предметов флаг в руки барабан на шею
...
Рейтинг: 0 / 0
19.09.2003, 10:38
    #32269957
Май (хо-о-о-рошенькая!!!)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
Для "Чукчи мы" и "kozin1":
Извините, отвлеклась - пыталась приготовить себе яичницу...(опять неудача - буду сидеть на диете), столько времени зря потеряла... Так вот, что такое "словарь" и "просто´та"?
А где В.С. я хочу, чтобы ОН мне объяснил!
...
Рейтинг: 0 / 0
19.09.2003, 11:24
    #32270036
assa
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
1. Вчера не заметил, что соврал.

В предложенном мной в "резюме" алгоритме НЕТ никакой рекурсии. После того, как мы число (+-)N раскидаем по 1 на N (старших по величине остатков от округления) слагаемых, остаток разноски будет равен 0. Процедура завершится.

2. Будет ли этот алгоритм наилучшим? Т.е. не стоит ли на какое-то слагаемое накинуть не 1, а 2-ку из остатка. (В том случае, когда "накидываются" ТОЛЬКО 1-ы, алгоритм, очевидно, "лучший" в смысле минимальности "абсолютной" погрешности. И, очевидно, для мимнимизации "абсолютной" погрешности он вообще наилучший (накидывать 2-ку на слагаемое заведомо хуже, чем по 1-е на 2). Можно так-же ранжировать не по "абсолютным" ошибкам округления, а по относительным. Вот для них вопрос: "а не стоило ли где-то накинуть 2-ку, а не 1-цу" остается открытым.

Итак, вопрос о решении с минимальной _относительной_ ошибкой разнесения ошибок округления:
расчетные величины:
b0, c0, d0 ... x0
величины после округления:
b, c, d ... x
величины абсолютных ошибок (округления точных "расчетных значений")
db=b-b0, dc = c-c0, ...
величины относительных ошибок округления
db/b0, dc/c0 ...
величина "прироста относительной ошибки" при добавлении 1-ы к какому-то слагаемому (оценка сверху - т.е. если добавляется не первая 1-а):
~1/x0...
...т.е. /если после округления "точного" решения неразнесенный остаток равен N/ нам надо ранжировать не только db/b0 ... dx/c0, но и
(dx+-1)/x0, (dx+-2)/x0... (dx+-N)/x0 (и только. и никаких переборов 100 чайников :0)
// ...Скорей всего, имеет смысл мимнимизировать (как это принято) сумму квадратов ошибок округления. т.е. ранжировать надо !квадраты! описанных величин//.

...Хотя опять вру: надо ранжировать величины:
ddXm**2 - ddX0**2, где ddXm = (dx+m)/x0 (-N<=m<=N)

После чего отнести величины m на X-вое слагаемое. (доказательство мимнимальности относительной ошибки предлагаемого решения предоставляется произвести самостоятельно)
...
Рейтинг: 0 / 0
19.09.2003, 14:19
    #32270333
АлексейК
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
2 Май

Думаю что именно это имел в виду Alexander G.
что имел ввиду я - путь останется загадкой ...
...
Рейтинг: 0 / 0
19.09.2003, 16:26
    #32270551
Владимир Саныч
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение суммы на несколько частей с точностью до целого
Май, я пришел.

Ты же "гидротехнику ни на что не променяешь" (вроде правильно цитирую, лень ссылку искать), так почему же ты не значешь, что такое геодезия? Неужели ты настолько хорошенькая, что не знаешь таких вещей?
...
Рейтинг: 0 / 0
Форумы / Microsoft Access [игнор отключен] [закрыт для гостей] / распределение суммы на несколько частей с точностью до целого / 19 сообщений из 19, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]