Фалшивите грамчета (задача за претегляне)
Задача:
На поличката са подредени в редица 128 тежести.
Всички истински тежести тежат по 100 грама.
В редицата има 4 фалшиви тежести по 99 грама,
намират се една до друга.
Имаме електронна везна - показва точното тегло на
предметите върху нея. Достатъчно голяма е да събере
и претегли всичките тежести.
Търси се минималният брой на претеглянията, за да се
отделят четирите фалшиви тежести.
Отговор: Фалшивите грамчета (задача за претегляне)
Цитат:
Първоначално публикувано от
ql^2/8 Задача:
На поличката са подредени в редица 128 тежести.
Всички истински тежести тежат по 100 грама.
В редицата има 4 фалшиви тежести по 99 грама,
намират се една до друга.
Имаме електронна везна - показва точното тегло на
предметите върху нея. Достатъчно голяма е да събере
и претегли всичките тежести.
Търси се минималният брой на претеглянията, за да се
отделят четирите фалшиви тежести.
Теглиш половината и ако отговаря грамажа със 5 бр. тегления.
Иначе от първия път - телиш и е ако е по-лек с 1, 2 или 3 гр. без значение вземаш последните от редичката (с колкото грама е по-лека) и съответно от другата редица вземаш разликата до 4 бр. (понеже са една до друга).
Отговор: Фалшивите грамчета (задача за претегляне)
Според мен може да стане и с четири претегляния.
От предложените от plimbostter може да обединим първите две претегления в едно.Тоест от 128 да стигнем до по-малко от 32.
Разделяме тежестите последователно на 5 групи.4 по 28 и една по 16.
На везната слагаме 70 тежести---> всички от първа група,21 от втора група(последователно вземаме 3 и една пропускаме,после пак вземаме 3 и една пропускаме и т.н.), от третата вземаме 14 (последователно вземаме 2 и 2 пропускаме,после пак вземаме 2 и 2 пропускаме и т.н.), от четвъртата вземаме 7 (последователно вземаме 1 и 3 пропускаме,после пак вземаме 1 и 3 пропускаме и т.н.), от петата нищо не вземаме.
В общия случай ако липсват 4гр. фалшивите са в първа група, ако липсват 3гр. фалшивите са в втора група, ако липсват 2гр. фалшивите са в трета група, ако липсва 1гр. фалшивите са в четвърта група, ако нищо не липсва фалшивите са в пета ,
Обаче фалшивите може едно временно да попадат в две групи,примерно първа и втора.Оттук следва ,че
ако липсват 4гр. фалшивите са от 1 до 31 позиция(31 позиции)
ако липсват 3гр. фалшивите са от 29 до 58 позиция(30 позиции)
ако липсват 2гр. фалшивите са от 56 до 85 позиция(30 позиции)
ако липсват 1гр. фалшивите са от 83 до 112 позиция(30 позиции)
ако нищо не липсва фалшивите са от 110 до 128 позиция(29 позиции).
Независимо дали се продължава с 31,30 или 29 тежести във второто теглене по-нататък се действа по предложения от plimbostter начин.
Отговор: Фалшивите грамчета (задача за претегляне)
Идеята е добра, но защо само веднъж?
* * *
Жокер:
128 е степен на двойката, но:
Фалшивите грамчета могат да са на 125 места,
а везните могат да показват 0, 1, 2, 3 или 4 грама
отклонение от очакваното (общо пет)...
Отговор: Фалшивите грамчета (задача за претегляне)
Ако по същия начин ако продължим и се опитаме да разделим група от 31,30 или 29 тежести на 5 или 4 подгрупи. Получават се групи ,които не са кратни на 4. Повтаряемостта през 4 малко губи смисъл..Ще се получи поредица по-голяма от 8 в която може да се намират фалшивите тежести. А при такава голяма поредица си губи смисъла този подход.
Отговор: Фалшивите грамчета (задача за претегляне)
Цитат:
Първоначално публикувано от
emil vasilev Ако по същия начин ако продължим и се опитаме да разделим група от 31,30 или 29 тежести на 5 или 4 подгрупи. Получават се групи ,които не са кратни на 4. Повтаряемостта през 4 малко губи смисъл..Ще се получи поредица по-голяма от 8 в която може да се намират фалшивите тежести. А при такава голяма поредица си губи смисъла този подход.
А може би първата стъпка може да се подобри?
Отговор: Фалшивите грамчета (задача за претегляне)
Отговор: Фалшивите грамчета (задача за претегляне)
1 теглене ако късмета ни е на MAX , 5 тегления ако е на MIN .
1 Прикачен файл(ове)
Отговор: Фалшивите грамчета (задача за претегляне)
Намерих начин за три претегления.
128 тежести ги разделяме на 5 групи - Първата с 28, останалите с 25.
От първата вземаме всичките тежести.
От втората - първата не вземаме,от втората започва последователността 3 вземаме,1 не вземаме и т.н.
От третата - първата не вземаме,от втората започва последователността 2 вземаме,2 не вземаме и т.н.
От четвъртата - първата не вземаме,от втората започва последователността 1 вземаме,3 не вземаме и т.н.
От петата нищо не вземаме.
Ако липсват 4гр. фалшивите са от позиция 1 до 28 --> 28 позиции.
Ако липсват 3гр. фалшивите са от позиция 27 до 53 --> 27 позиции.
Ако липсват 2гр. фалшивите са от позиция 52 до 78 --> 27 позиции.
Ако липсват 1гр. фалшивите са от позиция 77 до 103 --> 27 позиции.
Ако нищо не липсва фалшивите са от позиция 101 до 128 --> 28 позиции.
При второ теглене пак 5 групи - Първата от 7 или 8 (няма значение за логиката) и останалите 4 по 5.
Абсолютно същия подход се прилага.
Ако липсват 4гр. фалшивите са от позиция 1 до 8 --> 8 позиции.
Ако липсват 3гр. фалшивите са от позиция 7 до 13 --> 7 позиции.
Ако липсват 2гр. фалшивите са от позиция 12 до 18 --> 7 позиции.
Ако липсват 1гр. фалшивите са от позиция 17 до 23 --> 7 позиции.
Ако нищо не липсва фалшивите са от позиция 21 до 28 --> 8 позиции.
При трето теглене се изтеглят първите 4 и така се вижда къде точно е последователността.
Отговор: Фалшивите грамчета (задача за претегляне)
Емо ами ако фалшивите са на позиция 26,27,28 и 29 - ще покаже 3гр.отклонение и ще те подведе към група 2.
И на другите гранични места има проблем ако се намират фалшивите...
Отговор: Фалшивите грамчета (задача за претегляне)
Прав си поправям се. Но това не променя концепцията.
28 тежести ги разделяме на 5 групи - Първата с 28, останалите с 25.
От първата вземаме всичките тежести.
От втората - първата не вземаме,от втората започва последователността 3 вземаме,1 не вземаме и т.н.
От третата - първата не вземаме,от втората започва последователността 2 вземаме,2 не вземаме и т.н.
От четвъртата - първата не вземаме,от втората започва последователността 1 вземаме,3 не вземаме и т.н.
От петата нищо не вземаме.
Ако липсват 4гр. фалшивите са от позиция 1 до 28 --> 28 позиции.
Ако липсват 3гр. фалшивите са от позиция 26 до 53 --> 28 позиции.
Ако липсват 2гр. фалшивите са от позиция 51 до 78 --> 28 позиции.
Ако липсват 1гр. фалшивите са от позиция 76 до 103 --> 28 позиции.
Ако нищо не липсва фалшивите са от позиция 101 до 128 --> 28 позиции.
При второ теглене пак 5 групи - Първата от 8 и останалите 4 по 5.
Абсолютно същия подход се прилага.
Ако липсват 4гр. фалшивите са от позиция 1 до 8 --> 8 позиции.
Ако липсват 3гр. фалшивите са от позиция 6 до 13 --> 8 позиции.
Ако липсват 2гр. фалшивите са от позиция 11 до 18 --> 8 позиции.
Ако липсват 1гр. фалшивите са от позиция 16 до 23 --> 8 позиции.
Ако нищо не липсва фалшивите са от позиция 21 до 28 --> 8 позиции.
При трето теглене се изтеглят първите 4 и така се вижда къде точно е последователността.
Отговор: Фалшивите грамчета (задача за претегляне)
Цитат:
Първоначално публикувано от
emil vasilev Прав си поправям се. Но това не променя концепцията.
28 тежести ги разделяме на 5 групи - Първата с 28, останалите с 25.
От първата вземаме всичките тежести.
От втората - първата не вземаме,от втората започва последователността 3 вземаме,1 не вземаме и т.н.
От третата - първата не вземаме,от втората започва последователността 2 вземаме,2 не вземаме и т.н.
От четвъртата - първата не вземаме,от втората започва последователността 1 вземаме,3 не вземаме и т.н.
От петата нищо не вземаме.
Ако липсват 4гр. фалшивите са от позиция 1 до 28 --> 28 позиции.
Ако липсват 3гр. фалшивите са от позиция 26 до 53 --> 28 позиции.
Ако липсват 2гр. фалшивите са от позиция 51 до 78 --> 28 позиции.
Ако липсват 1гр. фалшивите са от позиция 76 до 103 --> 28 позиции.
Ако нищо не липсва фалшивите са от позиция 101 до 128 --> 28 позиции.
При второ теглене пак 5 групи - Първата от 8 и останалите 4 по 5.
Абсолютно същия подход се прилага.
Ако липсват 4гр. фалшивите са от позиция 1 до 8 --> 8 позиции.
Ако липсват 3гр. фалшивите са от позиция 6 до 13 --> 8 позиции.
Ако липсват 2гр. фалшивите са от позиция 11 до 18 --> 8 позиции.
Ако липсват 1гр. фалшивите са от позиция 16 до 23 --> 8 позиции.
Ако нищо не липсва фалшивите са от позиция 21 до 28 --> 8 позиции.
При трето теглене се изтеглят първите 4 и така се вижда къде точно е последователността.
Изглежда, че това е добро решение. Само да добавя, че в червено реда - обхвата е от 17 до 28 - понеже 16 и 17 има взети и няма как да са и двете фалшиви при липсва на 1гр... - но и така не се променя резултата...
Отговор: Фалшивите грамчета (задача за претегляне)
Значи при второто теглене вземам 1 до 8, 9 не вземам, вземам от 10 до 12, 13 и 14 не вземам ,15 и 16 вземам, 17,18 и 19 не вземам, 20 вземам, от 21 до 28 не вземам.
1 2 3 4 5 6 7 8
9 10 11 12 13
14 15 16 17 18
19 20 21 22 23
24 25 26 27 28
С червено са взетите за теглене.
Отговор: Фалшивите грамчета (задача за претегляне)
Цитат:
Първоначално публикувано от
emil vasilev Значи при второто теглене вземам 1 до 8, 9 не вземам, вземам от 10 до 12, 13 и 14 не вземам ,15 и 16 вземам, 17,18 и 19 не вземам, 20 вземам, от 21 до 28 не вземам.
1 2 3 4 5 6 7 8
9 10 11 12 13
14 15 16 17 18
19 20 21 22 23
24 25 26 27 28
С червено са взетите за теглене.
Да, верно...
- - - - - - - - - -
Моя подход беше с 4 групи (всяка по 32) - там се стигаше до решение с 3 тегления и в рядък но лош вариант до 4...
Отговор: Фалшивите грамчета (задача за претегляне)
Цитат:
Първоначално публикувано от
emil vasilev Значи при второто теглене вземам 1 до 8, 9 не вземам, вземам от 10 до 12, 13 и 14 не вземам ,15 и 16 вземам, 17,18 и 19 не вземам, 20 вземам, от 21 до 28 не вземам.
1 2 3 4 5 6 7 8
9 10 11 12 13
14 15 16 17 18
19 20 21 22 23
24 25 26 27 28
С червено са взетите за теглене.
Ако се построят групите по 8 (със застъпване по три), става по-ясeн шаблона.
(на първия ход групите са по 28, но изглеждат аналогично)
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 |
Иначе, браво! Това е решението.