Вверх ↑
Этот топик читают: Гость
Разработчик
Ответов: 25459
Рейтинг: 2070
#91: 2010-08-15 21:22:40 ЛС | профиль | цитата
Assasin писал(а):
Что тебе конкретно неясно?

Проехали, все ясно
карма: 19

0
Ответов: 750
Рейтинг: 111
#92: 2010-08-16 12:09:49 ЛС | профиль | цитата
nesco писал(а):
Не получится. Только 32, иначе -- висняк, и так на всех схемах, не толко моей. Мы с iarspider-ом пришли к выводу, что больше 20 проверять нецелесообразно, так что, никто из нас не выполнил условие задачи про предел в 100 акционеров, реальный предел у всех будет 31


Есть способ обойти эту проблему

Add(MultiElementEx,9528075,210,168)
{
@Hint=#8:задача 0|5:miver|12:Старшая Лига|
AddHint(-113,-53,72,39,@Hint)
}
BEGIN_SDK
Add(EditMultiEx,7593973,21,16)
{
WorkCount=#8:doProfit|
EventCount=#8:onProfit|
DataCount=#1:n|1:x|1:a|
Width=874
Height=438
link(doProfit,13920182:doEvent1,[(31,22)(31,111)])
}
Add(ArrayEnum,6329741,140,133)
{
onBreakEnable=0
link(onItem,12035960:doEvent1,[])
link(onEndEnum,1910856:doCompare,[(188,146)(188,297)])
link(Array,7593973:a,[(146,60)(41,60)])
}
Add(MathParse,11717053,831,403)
{
MathStr="%2*100/(%1)"
link(onResult,15296190:doWork3,[(875,409)])
link(X1,8564976:Var2,[])
link(X2,12788111:Var3,[(844,332)])
}
Add(If_else,11440149,231,140)
{
link(onTrue,6416852:doCompare,[])
link(onFalse,5004672:doCompare,[])
link(Op1,12061780:Result,[])
link(Op2,7593973:x,[(244,89)(34,89)])
}
Add(Math,12061780,231,49)
{
Op2=1
ResultType=0
link(Op1,5943023:Var,[])
}
Add(Hub,12035960,196,133)
{
link(onEvent1,12061780:doOperation,[(220,139)(220,55)])
link(onEvent2,11440149:doCompare,[])
}
Add(LineBreak,8993731,147,175)
{
Type=1
link(Data,6329741:Index,[])
Primary=[5943023,84,-154]
}
Add(Hub,13920182,40,105)
{
OutCount=5
link(onEvent1,2829215:In,[])
link(onEvent2,524848:In,[])
link(onEvent3,11168724:In,[])
link(onEvent4,15954020:In,[])
link(onEvent5,6329741:doEnum,[(97,139)(97,139)])
}
Add(Memory,9709550,653,140)
{
}
Add(ArrayRW,13488848,562,291)
{
link(onRead,2200601:doOperation,[])
link(Array,1372854:Array,[])
}
Add(If_else,1679845,693,347)
{
Type=4
Op2=Integer(50)
link(onTrue,3437342:doOperation,[])
}
Add(Hub,5835451,502,347)
{
link(onEvent1,6391908:doOperation,[])
link(onEvent2,2200601:doClear,[(602,360)(602,304)])
}
Add(Math,6391908,646,347)
{
Point(doClear)
link(onResult,1679845:doCompare,[])
link(Op1,5946607:Var2,[])
link(Op2,12788111:Var2,[])
}
Add(GetDataEx,12788111,653,327)
{
link(Data,15348641:Var2,[])
}
Add(LineBreak,8418310,516,253)
{
Caption="0"
link(Out,1372854:doClear,[])
Primary=[2829215,-439,-173]
}
Add(LineBreak,1350311,750,354)
{
Caption="1"
link(Out,3437342:doClear,[])
Primary=[524848,-673,-259]
}
Add(RealArray,1372854,562,239)
{
RealArray=[]
FileName="1.txt"
FileFormat=1
}
Add(LineBreak,3731059,517,305)
{
Caption="add"
link(Out,13488848:doAdd,[])
Primary=[10582169,-177,-158]
}
Add(GetDataEx,5946607,646,327)
{
Angle=3
link(Data,2200601:Result,[(617,332)])
}
Add(Math,2200601,611,291)
{
Point(doClear)
link(Op2,5946607:Var1,[(624,282)(652,282)])
}
Add(Math,3437342,796,347)
{
OpType=38
Default=100
Point(doClear)
link(Op2,8564976:Var1,[(809,339)(837,339)])
}
Add(GetDataEx,8564976,831,383)
{
Angle=3
link(Data,3437342:Result,[(802,388)])
}
Add(If_else,5004672,282,147)
{
Type=1
Op2=Integer(50)
link(onTrue,10582169:In,[])
link(onFalse,11474217:doValue,[(326,160)(326,174)])
}
Add(Memory,11474217,338,168)
{
Default=Integer(-1)
}
Add(If_else,6416852,387,140)
{
Type=1
Op2=Integer(50)
link(onTrue,9709550:doValue,[])
link(onFalse,7329091:doEvent1,[(451,153)(451,188)])
}
Add(Hub,4132134,325,298)
{
OutCount=3
link(onEvent1,8227263:doStart,[])
link(onEvent2,1693024:doRepeat,[])
link(onEvent3,11717053:doCalc,[(351,318)(351,409)])
}
Add(DoData,11551687,561,182)
{
Data=Integer(100)
link(onEventData,16270419:doWork2,[])
}
Add(HubEx,16270419,871,182)
{
Angle=3
link(onEvent,7593973:onProfit,[(875,22)])
}
Add(Hub,7329091,483,182)
{
link(onEvent1,11551687:doData,[])
link(onEvent2,409845:doWork,[])
}
Add(LineBreakEx,409845,509,189)
{
Caption="stop"
}
Add(LineBreakEx,3628676,40,154)
{
Caption="stop"
Type=1
link(OnEvent,6329741:doStop,[(85,160)(85,146)])
}
Add(If_else,1910856,275,291)
{
Type=5
Op2=Integer(-1)
link(onTrue,11241268:doCalc,[(325,297)(325,235)])
link(onFalse,4132134:doEvent1,[])
link(Op1,3121541:Var1,[(281,219)])
}
Add(MathParse,11241268,338,229)
{
MathStr="%2*100/(%1+%2)"
link(onResult,15296190:doWork2,[])
link(X1,3121541:Var2,[])
link(X2,15348641:Var1,[(351,219)])
}
Add(GetDataEx,3121541,338,214)
{
link(Data,11474217:Value,[])
}
Add(GetDataEx,15348641,653,214)
{
link(Data,9709550:Value,[])
}
Add(HubEx,15296190,871,229)
{
Angle=3
link(onEvent,16270419:doWork3,[])
}
Add(LineBreak,15269537,281,183)
{
Caption="2"
link(Out,11474217:doClear,[(325,189)(325,181)])
Primary=[11168724,-203,-73]
}
Add(GetDataEx,4143694,452,274)
{
Angle=1
link(Data,1372854:Count,[(575,279)])
}
Add(MultiElementEx,8227263,452,291)
{
link(onNext,13488848:doRead,[])
link(onEndNext,5835451:doEvent1,[(493,304)(493,353)])
link(n,4143694:Var2,[])
}
BEGIN_SDK
Add(EditMultiEx,14667209,21,21)
{
WorkCount=#7:doClear|7:doStart|6:doNext|
EventCount=#6:onNext|9:onEndNext|
VarCount=#4:Var2|
DataCount=#1:n|
Width=860
Height=424
VOffset=130
HOffset=200
link(doClear,665916:##clear,[])
link(doStart,665916:0step,[])
link(doNext,6306350:doEvent1,[(33,171)(33,178)])
link(Var2,3088594:Var2,[(227,427)(209,427)])
}
Add(MultiElementEx,665916,221,151)
{
link(addN+1,6904693:doEvent1,[])
link(Op1,12233088:Var2,[])
link(index,3981347:getVar,[])
}
BEGIN_SDK
Add(EditMultiEx,4319760,21,21)
{
WorkCount=#7:##clear|5:0step|5:##add|6:doNext|8:##select|7:doValue|
EventCount=#6:addN+1|
VarCount=#7:##count|7:##index|5:Count|
DataCount=#3:Op1|5:index|
Width=293
Height=193
VOffset=50
HOffset=200
Point(##clear)
Point(##add)
Point(##select)
Point(##count)
Point(##index)
link(0step,6198076:doWork2,[])
link(##add,16184906:doEvent1,[])
link(doNext,6298383:doNext,[(38,98)(38,112)])
link(##select,10638001:doWork3,[(74,105)])
link(doValue,6298383:doValue,[(34,112)(34,140)])
link(Count,6298383:Count,[(241,169)(120,169)])
}
Add(Counter,6298383,114,106)
{
Max=0
Point(Max)
Point(doMax)
Point(doValue)
link(onNext,14594902:doCompare,[])
link(Max,10498985:Var1,[(120,50)])
}
Add(If_else,14594902,221,106)
{
link(onTrue,4319760:addN+1,[(283,112)(283,77)])
link(Op1,545546:Result,[])
}
Add(GetDataEx,10498985,221,45)
{
link(Data,4319760:Op1,[])
}
Add(Math,545546,221,63)
{
OpType=1
link(Op1,10498985:Var2,[])
link(Op2,4319760:index,[])
}
Add(Hub,16184906,42,85)
{
link(onEvent1,6198076:doWork3,[(152,91)])
link(onEvent2,10638001:doWork2,[])
}
Add(HubEx,10638001,70,92)
{
link(onEvent,6298383:doMax,[(99,98)(99,133)])
}
Add(HubEx,6198076,148,78)
{
Angle=3
link(onEvent,545546:doOperation,[(152,69)])
}
END_SDK
Add(If_else,4308399,319,158)
{
link(onTrue,10597731:doWork2,[(399,164)(399,165)])
link(onFalse,13239160:doOperation,[])
link(Op1,10921789:Var,[])
link(Op2,13430739:Result,[])
}
Add(LineBreak,16229966,221,277)
{
Type=1
link(Data,2328870:Var2,[])
Primary=[10921789,98,-206]
}
Add(LineBreak,13496748,151,165)
{
Caption="add"
link(Out,665916:##add,[])
Primary=[11898554,343,-6]
}
Add(Hub,349488,459,159)
{
OutCount=3
link(onEvent1,11898554:In,[])
link(onEvent3,2633403:doWork2,[])
}
Add(HubEx,10225596,200,172)
{
link(onEvent,665916:doNext,[])
}
Add(For,2359529,116,340)
{
link(onEvent,1424702:doEvent1,[])
link(onStop,14301892:doEvent1,[(158,353)(158,367)])
link(End,1146642:Result,[])
}
Add(GetDataEx,2328870,221,263)
{
link(Data,665916:##count,[])
}
Add(Hub,1424702,165,340)
{
link(onEvent1,14490087:doWork3,[(197,346)])
link(onEvent2,2732475:doData,[])
}
Add(DoData,11006653,221,361)
{
Data=Integer(0)
link(onEventData,7482037:In,[])
}
Add(HubEx,3054557,193,179)
{
link(onEvent,665916:##select,[])
}
Add(LineBreak,15653780,153,179)
{
Caption="0"
link(Out,3054557:doWork2,[])
Primary=[7482037,117,182]
}
Add(Math,1146642,123,298)
{
OpType=1
Op2=1
ResultType=0
link(Op1,3088594:Var1,[(129,268)])
}
Add(Hub,3702658,81,333)
{
link(onEvent1,1146642:doOperation,[(109,339)(109,304)])
link(onEvent2,2359529:doFor,[])
}
Add(Math,13430739,326,116)
{
Op2=1
ResultType=0
link(Op1,10077841:getVar,[])
}
Add(Hub,6904693,291,151)
{
link(onEvent1,13430739:doOperation,[(315,157)(315,122)])
link(onEvent2,4308399:doCompare,[])
}
Add(Hub,9988477,431,180)
{
OutCount=3
link(onEvent1,14490087:doWork1,[(453,186)(453,241)])
link(onEvent2,10225596:doWork3,[(482,193)(482,258)(204,258)])
link(onEvent3,2633403:doWork3,[(519,200)])
}
Add(Math,13239160,375,165)
{
Op2=1
ResultType=0
link(onResult,9988477:doEvent1,[(419,171)(419,186)])
link(Op1,2681629:getVar,[])
}
Add(For,11602155,578,180)
{
Step=-1
link(onEvent,14367183:doOperation,[])
link(Start,5342214:Result,[])
}
Add(LineBreak,3732097,151,235)
{
link(Out,14490087:doWork2,[])
Primary=[10598819,623,-48]
}
Add(Math,5342214,578,138)
{
OpType=1
Op2=1
ResultType=0
link(Op1,7852567:getVar,[])
}
Add(Hub,27507,529,173)
{
link(onEvent1,5342214:doOperation,[(561,179)(561,144)])
link(onEvent2,11602155:doFor,[])
}
Add(Math,14367183,620,180)
{
Op2=1
ResultType=0
link(onResult,12793070:doCompare,[])
link(Op1,8674572:Var,[])
}
Add(LineBreak,13537302,319,206)
{
Caption="count"
Type=1
link(Data,5769687:Var3,[(325,201)])
Primary=[8674572,301,-54]
}
Add(DoData,4922315,809,194)
{
Data=Integer(0)
link(onEventData,665916:doValue,[(858,200)(858,249)(209,249)(209,192)])
link(Data,14367183:Result,[(815,189)(849,189)(849,235)(626,235)])
}
Add(HubEx,2633403,515,173)
{
link(onEvent,27507:doEvent1,[])
}
Add(If_else,12793070,662,180)
{
link(onTrue,10597731:doWork1,[(748,186)(748,97)(449,97)])
link(onFalse,126013:doEvent1,[])
link(Op1,12233088:Var3,[(668,65)])
}
Add(GetDataEx,12233088,221,60)
{
link(Data,14667209:n,[])
}
Add(Hub,126013,704,187)
{
link(onEvent1,3267686:doData,[])
link(onEvent2,4922315:doData,[])
}
Add(HubEx,10597731,445,159)
{
link(onEvent,349488:doEvent1,[])
}
Add(DoData,3267686,732,187)
{
Data=Integer(0)
link(onEventData,10598819:In,[])
link(Data,11602155:Position,[(738,175)(723,175)(723,220)(584,220)])
}
Add(Hub,14301892,165,361)
{
link(onEvent1,11006653:doData,[])
link(onEvent2,14667209:onEndNext,[(871,374)(871,164)])
}
Add(Hub,6306350,46,172)
{
link(onEvent1,10225596:doWork2,[])
link(onEvent2,3702658:doEvent1,[(70,185)(70,339)])
}
Add(LineBreakEx,2681629,375,137)
{
Caption="i"
Type=2
}
Add(LineBreakEx,7852567,578,110)
{
Caption="i"
Type=2
}
Add(LineBreakEx,1271693,228,207)
{
Caption="i"
Type=3
link(_Data,665916:##index,[])
}
Add(LineBreakEx,3981347,228,126)
{
Caption="i"
Type=2
}
Add(LineBreakEx,10077841,326,92)
{
Caption="i"
Type=2
}
Add(HubEx,14490087,193,235)
{
Angle=3
link(onEvent,3054557:doWork3,[])
}
Add(GetDataEx,3088594,203,263)
{
Angle=1
link(Data,2328870:Var1,[])
}
Add(GetDataEx,5769687,301,196)
{
Angle=3
link(Data,665916:Count,[(241,201)])
}
Add(DoData,2732475,301,347)
{
Data=Integer(0)
link(onEventData,14667209:onNext,[(867,353)(867,157)])
link(Data,5769687:Var2,[(307,292)(307,292)])
}
END_SDK
Add(Repeat,1693024,364,305)
{
Type=2
link(onRepeat,8227263:doNext,[])
link(Op1,4143694:Var1,[(370,279)])
link(Op2,8227263:Var2,[(377,293)(405,293)(405,338)(458,338)])
}
Add(LineBreak,5941198,409,291)
{
Caption="3"
link(Out,8227263:doClear,[])
Primary=[15954020,-332,-167]
}
END_SDK


карма: 1

0
Разработчик
Ответов: 25459
Рейтинг: 2070
#93: 2010-08-16 12:26:52 ЛС | профиль | цитата
miver, никто не спорит, что можно обойти, применив битовую арифметику, но прикинь время исполнения ПО при 100 акционерах
карма: 19

0
Ответов: 8325
Рейтинг: 775
#94: 2010-08-16 16:09:34 ЛС | профиль | цитата
nesco, хотя пора завязывать с обсуждением, но всё таки: iarspider не полностью раскрыл условия задачи, для полного перебора всех вариантов при 100 акционерах не хватит жизни, алгоритма обхода полного перебора, наверное, нет, значит надо в условии поставить ограничитель, например, 50.01% - тогда можно поискать и быстрый алгоритм (правда в жизни подобные задачи не требуют быстроты, скорее точности )
карма: 14

0
Разработчик
Ответов: 25459
Рейтинг: 2070
#95: 2010-08-16 16:21:53 ЛС | профиль | цитата
Леонид писал(а):
для полного перебора всех вариантов при 100 акционерах не хватит жизни

Про что я и спросил miver-a
nesco писал(а):
прикинь время исполнения ПО при 100 акционерах

------------ Дoбавленo в 16.21:
Леонид писал(а):
хотя пора завязывать с обсуждением

Зачем же нас лишать такого удовольствия, как общение с умными людьми
карма: 19

0
Ответов: 16461
Рейтинг: 1211
#96: 2010-08-16 16:40:03 ЛС | профиль | цитата
Леонид, а если
1. предварительная сортировка списка % акций по убыванию или возрастанию.
2. первое значение нужной добавки = 50% - имеющиеся%
3. всё, что больше нужных % - долой и т.д.


карма: 22
Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!
0
Разработчик
Ответов: 25459
Рейтинг: 2070
#97: 2010-08-16 16:45:22 ЛС | профиль | цитата
Tad писал(а):
а если предварительная сортировка списка % акций по убыванию

Можно пойти дальше и исключить из расчета явно несостоявшиеся коалиции, используя сортировку по убыванию
карма: 19

0
Ответов: 750
Рейтинг: 111
#98: 2010-08-16 16:45:41 ЛС | профиль | цитата
Леонид писал(а):
nesco, хотя пора завязывать с обсуждением, но всё таки: iarspider не полностью раскрыл условия задачи, для полного перебора всех вариантов при 100 акционерах не хватит жизни, алгоритма обхода полного перебора, наверное, нет, значит надо в условии поставить ограничитель, например, 50.01% - тогда можно поискать и быстрый алгоритм (правда в жизни подобные задачи не требуют быстроты, скорее точности )


Почему так категорично. Посмотри на результаты в источнике тут
карма: 1

0
Разработчик
Ответов: 25459
Рейтинг: 2070
#99: 2010-08-16 16:49:05 ЛС | профиль | цитата
miver писал(а):
Почему так категорично

Это не я писал. Но, сказано же конкретно
Леонид писал(а):
при 100 акционерах не хватит жизни, алгоритма обхода полного перебора

Я же тебя спросил
nesco писал(а):
прикинь время исполнения ПО при 100 акционерах

добавлю -- методом полного перебора, а не алгоритмом быстрого поиска
карма: 19

0
Ответов: 750
Рейтинг: 111
#100: 2010-08-16 16:52:52 ЛС | профиль | цитата
nesco писал(а):
Я же тебя спросил
nesco писал(а)
прикинь время исполнения ПО при 100 акционерах

добавлю -- методом полного перебора, а не алгоритмом быстрого поиска


примерно 3.22E+17 лет на моем компъютере

карма: 1

0
Разработчик
Ответов: 25459
Рейтинг: 2070
#101: 2010-08-16 16:54:45 ЛС | профиль | цитата
miver писал(а):
примерно 3.22E+17 лет на моем компъютере

Это при том, что Вселенная существует, приблизительно, 1.4E+10 лет
Тут не только нашей, но и жизни Вселенной может не хватить, далеко не факт, что она может просуществовать еще 3.22E+17 лет
карма: 19

0
Ответов: 16461
Рейтинг: 1211
#102: 2010-08-16 16:57:30 ЛС | профиль | цитата
nesco писал(а):
используя сортировку по убыванию
Тут подумать надо - удалять из StrList удобнее с конца.
карма: 22
Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!
0
Ответов: 750
Рейтинг: 111
#103: 2010-08-16 16:57:57 ЛС | профиль | цитата
miver писал(а):
Почему так категорично

Я писал про вот что
Леонид писал(а):
алгоритма обхода полного перебора, наверное, нет

а такой алгоритм точно есть, по ссылке выше видно время расчета
карма: 1

0
Разработчик
Ответов: 25459
Рейтинг: 2070
#104: 2010-08-16 16:59:18 ЛС | профиль | цитата
miver писал(а):
а такой алгоритм точно есть, по ссылке выше видно время расчета

Есть такие алгоритмы, но не факт, что они являются точными алгоритмами, а не вероятностными
miver, предлагаю тебе порыться в первоисточниках и почитать диссертации по этому вопросу, глядишь и метод откопается
карма: 19

0
Ответов: 750
Рейтинг: 111
#105: 2010-08-16 17:08:29 ЛС | профиль | цитата
nesco писал(а):
Есть такие алгоритмы, но не факт, что они являются точными алгоритмами, а не вероятностными

Приведу пример
пусть есть список акционеров (30,40,10,9,8,7,6,5,4,1), нуж акционер скажем 4-й
1. Проверяем есть ли акционер с процентом >50
2. Сортируем список --> (40,30,10,8,7,6,5,4,1)
3. Начинаем перебор, хитрым способом по индексам
1
2
3
4
5
6
7
8
9
10
1,2
1,3
1,4
1,5
1,6
1,7
1,8
1,9
1,10
2,3
2,4
и т.д.
При каждой итерации проверяем больше ли 50 сумма, если менше то нужно увелчивать разряд перебора (при индексе = 1, сумма = 40 переходим на индекс 1,2)

Таким способом сразу отсеем все решения менше 50
карма: 1

0
Сообщение
...
Прикрепленные файлы
(файлы не залиты)