roboforum.ru

Да там к конечным рядам все должно сводиться по идее.
Поиск в ширину, наверное, неплох, да... если по памяти ограничений нет.
Я бы все-таки предрасчитал пары-тройки номиналов, честно...

dccharacter, Не, такие гирлянды никуда не годятся

Простой перебор :

Код: Выделить всё • Развернуть

D/ResistorCalc(19279): Target value: 575675677,000000
D/ResistorCalc(19279): Solution size: 7
D/ResistorCalc(19279):   solution[0]=560000000,000000
D/ResistorCalc(19279):   solution[1]=15000000,000000
D/ResistorCalc(19279):   solution[2]=620000,000000
D/ResistorCalc(19279):   solution[3]=51000,000000
D/ResistorCalc(19279):   solution[4]=4300,000000
D/ResistorCalc(19279):   solution[5]=330,000000
D/ResistorCalc(19279):   solution[6]=47,000000
D/ResistorCalc(19279): Sum=575675677,000000, Error=0,000000

Код: Выделить всё • Развернуть

D/ResistorCalc(19467): Target value: 56757567,700000
D/ResistorCalc(19467): Solution size: 6
D/ResistorCalc(19467):   solution[0]=56000000,000000
D/ResistorCalc(19467):   solution[1]=750000,000000
D/ResistorCalc(19467):   solution[2]=7500,000000
D/ResistorCalc(19467):   solution[3]=62,000000
D/ResistorCalc(19467):   solution[4]=5,600000
D/ResistorCalc(19467):   solution[5]=0,100000
D/ResistorCalc(19467): Sum=56757567,700000, Error=0,000000

Добавлено спустя 1 минуту 9 секунд:

Madf писал(а):в андроид маркете есть готовые приложения (наша и забугорная)

Два резистора я и на калькуляторе посчитаю. И как мне эти программы в свою запихивать?

Michael_K писал(а):Да там к конечным рядам все должно сводиться по идее.
Поиск в ширину, наверное, неплох, да... если по памяти ограничений нет.
Я бы все-таки предрасчитал пары-тройки номиналов, честно...

>>> ================================ RESTART ================================
>>>
Please enter target resistance: 45676.7
num expanded: 9
Solution: 45676.6 , resistors used: (1.0, 43000.0, 2400.0, 270.0, 5.6)
Error is: 0.0999999999985 (0.000219%)
>>> ================================ RESTART ================================
>>>
Please enter target resistance: 34534534.456
num expanded: 27
Solution: 34534534.4 , resistors used: (1.0, 9100000.0, 9100000.0, 9100000.0, 6800000.0, 430000.0, 4300.0, 220.00000000000003, 11.0, 2.4)
Error is: 0.0560000017285 (0.000000%)
>>>

Добавлено спустя 58 секунд:

blindman писал(а):dccharacter, Не, такие гирлянды никуда не годятся

Они очень даже годятся. Под бесконечные ряды элементарно модифицируется.

Ну когда модифицируется, тогда и можно разговаривать.

dccharacter писал(а):num expanded: 27

И что это значит?

Michael_K писал(а):

dccharacter писал(а):num expanded: 27

И что это значит?

Это значит количество итераций...

Добавлено спустя 2 минуты 9 секунд:

blindman писал(а):Ну когда модифицируется, тогда и можно разговаривать.

ну а раз сейчас нельзя, тогда, конечно, перебором.
Вот радует меня: давайте придумаем какую-нибудь космическую задачу, спросим как ее решать, получим ответ, а потом будет долго рассказывать, какой это ответ неправильный.

dccharacter писал(а):

Michael_K писал(а):

dccharacter писал(а):num expanded: 27

И что это значит?

Это значит количество итераций...

Все равно не понятно.
Алгоритм попробовал всего 27 цепочек? Или ветвей от корня? Или вообще ветвей - и от корня, и промежуточных?
Или чего-то еще... что вы называете "итерацией"?

Вы сейчас говорите ничуть не лучше, чем у вас в подписи

Добавлено спустя 6 минут 35 секунд:
Вы, видимо, не понимаете, чего блайндман хочет.
Он хочет быстрый алгоритм... Не просто быстрый, а супер-пупер-быстрый...
Ну, там, в гугль или в какой-нибудь самсунг на конкурс.

Там любят такие задачки задавать. Типа, проанализировать дофигаллиард чисел на простоту. Кто сделает быстрее, того возьмем дворником...

ок

dccharacter писал(а):получим ответ

Я не заметил. Можно повторить?

>>> ================================ RESTART ================================
>>>
Solution: 575675677.0 , resistors used: [560000000.0, 15000000.0, 620000.0, 51000.0, 3900.0, 27.0, 750.0] , size: 7
Error is: 0.0 (0.000000%)
Nodes expanded: 168
>>> ================================ RESTART ================================
>>>
Solution: 54.0 , resistors used: [3.0, 51.0] , size: 2
Error is: 0.0 (0.000000%)
Nodes expanded: 43
>>> ================================ RESTART ================================
>>>
Solution: 540.0 , resistors used: [30.0, 509.99999999999994] , size: 2
Error is: 0.0 (0.000000%)
Nodes expanded: 67
>>> ================================ RESTART ================================
>>>
Solution: 5.75675677567e+11 , resistors used: [560000000000.0, 15000000000.0, 620000000.0, 51000000.0, 4300000.0, 360000.0, 16000.0, 1300.0, 27.0, 240.0] , size: 10
Error is: 0.0 (0.000000%)
Nodes expanded: 718
>>> ================================ RESTART ================================
>>>
Solution: 56757567.7 , resistors used: [56000000.0, 750000.0, 6800.0, 2.7, 15.0, 750.0] , size: 6
Error is: 0.0 (0.000000%)
Nodes expanded: 2634
>>>

К сожалению, я не уверен, что решение верное, так как не могу доказать, что эвристика верная (это необходимо, чтобы гарантировать оптимальное решение). Я уже на это напоролся, мое предыдущее решение давало ответ из восьми резисторов, когда надо было копать дальше и искать цепь из семи резисторов.
Ладно, хоть не скучно было.

Добавлено спустя 3 минуты 30 секунд:
Вот для теста:

Target: 0.844421851525
Solution: 0 , resistors used: [] , size: 0
Error is: 0.844421851525 (100.000000%)
Nodes expanded: 1


Target: 7.5795440294
Solution: 7.5 , resistors used: [7.5] , size: 1
Error is: 0.079544029403 (1.049457%)
Nodes expanded: 1


Target: 42.0571580831
Solution: 42.0 , resistors used: [39.0, 3.0] , size: 2
Error is: 0.0571580830845 (0.135906%)
Nodes expanded: 2


Target: 258.916750293
Solution: 258.9 , resistors used: [240.0, 15.0, 3.9] , size: 3
Error is: 0.0167502929634 (0.006469%)
Nodes expanded: 6


Target: 5112.74721369
Solution: 5112.7 , resistors used: [5100.0, 9.1, 3.6] , size: 3
Error is: 0.0472136860844 (0.000923%)
Nodes expanded: 9


Target: 40493.413745
Solution: 40493.4 , resistors used: [39000.0, 1300.0, 180.0, 4.3, 9.1] , size: 5
Error is: 0.0137450414259 (0.000034%)
Nodes expanded: 19


Target: 783798.589035
Solution: 783798.5 , resistors used: [750000.0, 33000.0, 750.0, 47.0, 1.5] , size: 5
Error is: 0.0890347725945 (0.000011%)
Nodes expanded: 7


Target: 3033127.26079
Solution: 3033127.2 , resistors used: [3000000.0, 33000.0, 110.00000000000001, 15.0, 2.2] , size: 5
Error is: 0.0607892745174 (0.000002%)
Nodes expanded: 31


Target: 47659695.4152
Solution: 47659695.4 , resistors used: [47000000.0, 620000.0, 39000.0, 680.0, 13.0, 2.4] , size: 6
Error is: 0.0152355805039 (0.000000%)
Nodes expanded: 21


Target: 583382039.455
Solution: 583382039.4 , resistors used: [560000000.0, 22000000.0, 1300000.0, 82000.0, 27.0, 6.2, 6.2] , size: 7
Error is: 0.0550310611725 (0.000000%)
Nodes expanded: 108


Target: 9081128851.95
Solution: 9081128851.9 , resistors used: [8199999999.999999, 819999999.9999999, 56000000.0, 5100000.0, 27000.0, 1800.0, 39.0, 4.7, 8.2] , size: 9
Error is: 0.053352355957 (0.000000%)
Nodes expanded: 124


Target: 50468685581.7
Solution: 50468685581.7 , resistors used: [47000000000.0, 3300000000.0, 160000000.0, 8199999.999999999, 470000.0, 15000.0, 560.0, 1.3, 2.4, 18.0] , size: 10
Error is: 0.0390243530273 (0.000000%)
Nodes expanded: 262


Target: 2.818378444e+11
Solution: 2.818378444e+11 , resistors used: [270000000000.00003, 11000000000.0, 819999999.9999999, 16000000.0, 1800000.0, 43000.0, 1300.0, 75.0, 4.7, 20.0] , size: 10
Error is: 0.00384521484375 (0.000000%)
Nodes expanded: 78


Target: 7.55804204157e+12
Solution: 7.55804204157e+12 , resistors used: [7500000000000.0, 56000000000.0, 2000000000.0, 39000000.0, 3000000.0, 39000.0, 2400.0, 150.0, 2.2, 20.0] , size: 10
Error is: 0.0390625 (0.000000%)
Nodes expanded: 56


Target: 6.18368996675e+13
Solution: 6.18368996675e+13 , resistors used: [56000000000000.0, 5600000000000.0, 220000000000.00003, 16000000000.0, 819999999.9999999, 75000000.0, 4300000.0, 360000.0, 7500.0, 24.0, 9.1] , size: 11
Error is: 0.0625 (0.000000%)
Nodes expanded: 21

Понятно. Когда мне надо найти решение, я отправляю вам исходные данные, а вы публикуете ответ

Не понимаю я этого...

По-моему, во-первых, всегда достижима абсолютная точность.
(ряд резисторов бесконечный, а точность мантиссы ограничена).
Откуда в последнем, например, "тесте" взялось 9.1, если 6.18368996675e+13 - кончается вообще на два нуля ??? Еще и ошибка какая-то осталась!

Во-вторых, по-моему, имеет смысл выкинуть плавающую точку нафиг. Считать только мантиссу в целых чмслах или даже как строку. Так увеличится скорость, не будет потерь точности и не нужно будет делать всякие "финты ушами".

В-третьих, я почти убежден, что считать можно последовательно-поразрядно.
Например, в ряду 1,2,3,...,99,100 все значения набираются из одного или двух резисторов из ряда E24, кроме значения 96 - для него надо три резистора. До тысячи - ни одной четверки не попадается!

То есть по предрасчитанной коротенькой табличке мы сразу можем откинуть два-три старших разряда мантиссы. Без поиска вообще!

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

Michael_K писал(а):всегда достижима абсолютная точность

Только при неограниченной длине цепочки

Michael_K писал(а):То есть по предрасчитанной коротенькой табличке мы сразу можем откинуть два-три старших разряда мантиссы. Без поиска вообще!

Без гарантий, что в итоге получим оптимальное решение

blindman писал(а):

Michael_K писал(а):всегда достижима абсолютная точность

Только при неограниченной длине цепочки

Какой цепочки? Резисторов? Это не так. Я же только что показал, что при ограниченной мантиссе требуемого резистора число резисторов ряда E24 тоже ограничено. Берем первую цифру мантиссы - заменяем набором резисторов (одним или двумя), берем вторую и т.п.

Или у вас заданное сопротивление это бесконечная дробь? Или вообще иррациональное? Тогда тем более поразрядно надо считать!
Оно (заданное сопротивление) откуда вообще берется?

blindman писал(а):

...сразу можем откинуть два-три старших разряда мантиссы. Без поиска вообще!

Без гарантий, что в итоге получим оптимальное решение

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

А можно ссылку на оригинальную задачу? (в личку можно)...

Это и есть оригинальная задача. В гугл меня дворником не возьмут, да я и не стремлюсь.

Michael_K писал(а):Я же только что показал, что при ограниченной мантиссе требуемого резистора число резисторов ряда E24 тоже ограничено

Одно из условий - N задано. Решение должно содержать не более N элементов.