|
|
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
есть задача: распределение некоторой целой суммы на несколько частей с точностью до целой части. причем сумма получившихся частей должна быть равна начальной сумме. Все хорошо когда все делится на целое число , но когда остаток ... я принял следующую методику Код: plaintext 1. 2. 3. есть ли математические способы решения данной задачи ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2003, 09:25 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
Когда я изучал геодезию, там алгоритм был почти такой же. Только пункт 4 выглядел иначе: раскидывали по 1 по всем частям, начиная с самой большой. Только там пункта 1 не было. Если просто делить, то части будут одинаковые, самой большой части не будет. Пример: 7+8+11=26, а надо 28. Значит, добавляем по 1 к 11 и к 8. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2003, 17:01 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
можете раскидать и _"дробь"_ /а не _целое_/. А разницу между входящим и остатком отнести на наибольшее. ТщательнеЕ получится. Это, как я понимаю, "раскидывание " ошибок округления по НДС - ам и т.п.? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2003, 18:21 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
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 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2003, 18:40 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
спасибо, кончно ... но я в душе надеялся что мало ли есть в форуме - гений - математик который предложил бы решение в одну строку - математической формулой способ саныча достаточно интересный но в моем случае не подойдет так как в большинстве случаев у меня одна часть более 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 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2003, 19:00 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
А что не понятно? Я ж не читал задачку: ) А понял: "раскидать сумму по частям". _____________ Поразмышляем о целочисленной математике: есть величина 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). _____ ЗЫ: Можно пользоваться целочисленным делением, но и при разнесении остатков пользоваться не обычным "старшинством" по величине, а сравнением остатков от целочисленного деления. (а вот чего и на что - надо покумекать, но в лом-с - пьян-с). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2003, 19:41 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
если assa прав... то есть такое понятие как НДС внутри, и НДС сверху . может использовать это? у меня есть такая параметра на форме . для каждого клиента можно сделать накладную либо - цена целое, цена с ндс как получится либо цена с ндс целое, цена -как получится. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2003, 19:51 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
Владимир Саныч А чё такэ "Когда я изучал геодезию... ". Новое слово какое-то... "Гео" - понятно, что-то земное, а вот "-де" (de чего?)?! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2003, 09:13 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
Класс!!! Новое слово! В словарь загляни. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2003, 09:20 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
некоторая степень "простоты" украшает девушку. написано ведь. хорошенькая. не будем строги. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2003, 09:26 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
>нужно что-то логическое - такое чтоб давало минимальную погрешность так а если использовать твой же алгоритм >1 делю на части с округлением >2 считаю сумму получившегося >3 считаю разницу между исходным значением и суммой частей - получаю +/- >остаток >4 +/- остаток отношу к самой большой части только 1 и 4 пункт заменить на 1_new. делю на части с отсечением 4_new. + остаток отношу к части у которой максимально отношение дробной части к целой. имхо, это и будет минимальная погрешность. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2003, 09:30 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
2 sasa только нужно еще будет добавить учет погрешности для каждой записи и пересчет ее с добавлением каждой единицы - так как бывает нужно +/-1 или +/-2 итд. для достижения правильной суммы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2003, 09:38 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
в математике это называется задача рюкзака пример емкость =100 есть предметы объемом 34, 32, 29 ,,, 3 в рюкзак надо засунуть мах объем ( вес) самый простой алгоритм предметы отсортированы по объему while пытаемся положить в рюкзак самый большой предмет который может влезть проверяем оставшийся объем loop Алексей оставшуюся часть может разнести к любому предмету для числа предметов 10-20 можно пробовать полный перебор вариантов на большой размерности резко возрастает число вариантов задача NP полная ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2003, 09:47 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
в математике это называется задача рюкзака пример емкость =100 есть предметы объемом 34, 32, 29 ,,, 3 в рюкзак надо засунуть мах объем ( вес) самый простой алгоритм предметы отсортированы по объему while пытаемся положить в рюкзак самый большой предмет который может влезть проверяем оставшийся объем loop Я так понял не самый лучший алгоритм :) Скажем предметы объемом 75, 33, 33, 33.... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2003, 09:49 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
лучшим алгоритмом может быть только полный перебор вариантов для 100 предметов флаг в руки барабан на шею ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2003, 10:10 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
Для "Чукчи мы" и "kozin1": Извините, отвлеклась - пыталась приготовить себе яичницу...(опять неудача - буду сидеть на диете), столько времени зря потеряла... Так вот, что такое "словарь" и "просто´та"? А где В.С. я хочу, чтобы ОН мне объяснил! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2003, 10:38 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
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-вое слагаемое. (доказательство мимнимальности относительной ошибки предлагаемого решения предоставляется произвести самостоятельно) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2003, 11:24 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2003, 14:19 |
|
||
|
распределение суммы на несколько частей с точностью до целого
|
|||
|---|---|---|---|
|
#18+
Май, я пришел. Ты же "гидротехнику ни на что не променяешь" (вроде правильно цитирую, лень ссылку искать), так почему же ты не значешь, что такое геодезия? Неужели ты настолько хорошенькая, что не знаешь таких вещей? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2003, 16:26 |
|
||
|
|

start [/forum/topic.php?fid=45&msg=32269594&tid=1679351]: |
0ms |
get settings: |
9ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
59ms |
get topic data: |
9ms |
get forum data: |
3ms |
get page messages: |
58ms |
get tp. blocked users: |
1ms |
| others: | 198ms |
| total: | 358ms |

| 0 / 0 |
