ReSQL.ru
     
powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм
21 сообщений из 21, страница 1 из 1
Алгоритм
    #32959659
Уртьев Федя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Уртьев Федя
Гость
Как из 13 монет(там есть ровно 1 фальшивая, с другим весом) за 3 взвешивания на чашечных весах определить ту фальшивую?
...
Рейтинг: 0 / 0
14.03.2005, 19:27
| Ответить | Цитировать | Написать  
Алгоритм
    #32959673
miniСЛОН
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miniСЛОН
Гость
Уртьев ФедяКак из 13 монет(там есть ровно 1 фальшивая, с другим весом) за 3 взвешивания на чашечных весах определить ту фальшивую?
подели по 6 штук и их взвесь, дальше сам подумай
...
Рейтинг: 0 / 0
14.03.2005, 19:35
| Ответить | Цитировать | Написать  
Алгоритм
    #32959677
Уртьев Федя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Уртьев Федя
Гость
miniСЛОН Уртьев ФедяКак из 13 монет(там есть ровно 1 фальшивая, с другим весом) за 3 взвешивания на чашечных весах определить ту фальшивую?
подели по 6 штук и их взвесь, дальше сам подумай

И что дальше, если две половины не равны?
...
Рейтинг: 0 / 0
14.03.2005, 19:37
| Ответить | Цитировать | Написать  
Алгоритм
    #32959678
miniСЛОН
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miniСЛОН
Гость
miniСЛОН Уртьев ФедяКак из 13 монет(там есть ровно 1 фальшивая, с другим весом) за 3 взвешивания на чашечных весах определить ту фальшивую?
подели по 6 штук и их взвесь, дальше сам подумай
пардон, фигню сморозил
...
Рейтинг: 0 / 0
14.03.2005, 19:39
| Ответить | Цитировать | Написать  
Алгоритм
    #32959693
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
Предполагается, что фальшивая легче настоящих. Тогда:
1.Оставляешь одну в сторону, делишь другие на 2 группы по 6 и ставишь на обе чашки весов. Если равенство- значит фальшивая та, одна. Если нет- фальшивая там где более легкая группа.
2.Делишь ту группу на 2 по 3 и взвешиваешь. Берешь ту тройку, которая легче, отставляешь одну монету и... см. 1
...
Рейтинг: 0 / 0
14.03.2005, 19:53
| Ответить | Цитировать | Написать  
Алгоритм
    #32959695
Уртьев Федя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Уртьев Федя
Гость
S.G.Предполагается, что фальшивая легче настоящих.

А если не Предполагается ? Насчёт легче или тяжелее ничего не известно!
...
Рейтинг: 0 / 0
14.03.2005, 19:55
| Ответить | Цитировать | Написать  
Алгоритм
    #32959721
dbhost
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dbhost
Гость
Бородатая задача
Поищи ответы в гугле

з.ы. вообще-то вопрос немного не по теме форума
...
Рейтинг: 0 / 0
14.03.2005, 20:14
| Ответить | Цитировать | Написать  
Алгоритм
    #32959797
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
имхо алгоритмы имеет прямое отношение к программированию
...
Рейтинг: 0 / 0
14.03.2005, 21:44
| Ответить | Цитировать | Написать  
Алгоритм
    #32959895
alex_k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex_k
Участник
более того.
наверное, на основании этого алгоритма существует какой нибудь продвинутый поисковый алгоритм :-)
...
Рейтинг: 0 / 0
15.03.2005, 03:02
| Ответить | Цитировать | Написать  
Алгоритм
    #32960132
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
Уртьев Федя
А если не Предполагается ? Насчёт легче или тяжелее ничего не известно!Фальшивая монета- это когда в ней меньше металла. ОК, поищи в интернете и скажи, мне тоже интересно решение.
...
Рейтинг: 0 / 0
15.03.2005, 10:15
| Ответить | Цитировать | Написать  
Алгоритм
    #32960301
foo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
foo
Гость
А давайте другую задачку порешаем. Решение элементарное - но думал я долго :)

Дано: 9 мешков золотых монет + 1 мешок с фальшивыми монетами, которые легче (ну ведь они, всё же, фальшивые!) на 1 грамм.
Каждая настоящая монета весит.. ну пусть 30 грамм, а фальшивая - соответственно - 29 грамм.

Ко всему этому хозяйству у нас есть ВЕСЫ! на которых мы можем произвести только ОДНО взвешивание.

Требуется: за ОДНО взвешивание определить в каком мешке фальшивые монеты.

Enter. :)
...
Рейтинг: 0 / 0
15.03.2005, 11:18
| Ответить | Цитировать | Написать  
Алгоритм
    #32960322
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
А давайте другую задачку порешаем. Решение элементарное - но думал я долго :)

Весы могут показывать вес?? )

ну я думаю что-то типа :

взять из кажного i-того мешка i монет

(1 2 3 4 ..n)

недостающий вес до n(n+1)/2 * 30
даст как раз номер мешка в котором зарыта бага..
...
Рейтинг: 0 / 0
15.03.2005, 11:24
| Ответить | Цитировать | Написать  
Алгоритм
    #32960347
foo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
foo
Гость
Палестинецнедостающий вес до n(n+1)/2 * 30
даст как раз номер мешка в котором зарыта бага..

Правильно :) Шустро вы , однако :)
...
Рейтинг: 0 / 0
15.03.2005, 11:30
| Ответить | Цитировать | Написать  
Алгоритм
    #32965259
Уртьев Федя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Уртьев Федя
Гость
Имеется 13 монет, из них ровно одна фальшивая, причем неизвестно, легче она настоящих или тяжелее. Требуется найти эту монету за три взвешивания. Весы - стандартные для задач этого типа: две чашечки без гирь.

Ответ: Отложим в сторону тринадцатую монету, а остальные обозначим следующим образом: FAKE MIND CLOT
Теперь взвешиваем одну четверку против другой (буквы обозначают монеты, входящие в каждую четверку): MA DO - LIKE, ME TO - FIND, FAKE - COIN. Теперь совершенно просто найти фальшивую монету, если она входит в эти двенадцать монет. К примеру, если результаты взвешивания были: слева легче, равно, слева легче, то фальшивой может быть только монета "A", которая легче других.
А что если фальшивой окажется все-таки отложенная нами, тринадцатая монета? Все очень просто: в этом случае при всех трёх взвешиваниях весы будут сбалансированы. К сожалению в этом случае нам не узнать легче или тяжелее тринадцатая монета, но в условии такого требования и не было :)


Есть ли решение попроще? :-)
...
Рейтинг: 0 / 0
17.03.2005, 11:09
| Ответить | Цитировать | Написать  
Алгоритм
    #32967163
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
только не говори, что сам придумал.
три взвешивания дают 27 последовательностий из {oo, лт, тл}
а вариантов только 12.

два взвешивания явно мало - будет 9 последовательностей.
...
Рейтинг: 0 / 0
18.03.2005, 03:10
| Ответить | Цитировать | Написать  
Алгоритм
    #32967164
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
oo - одинаково одинаково
лт - легче тяжелее
тл - тяжелее легче
...
Рейтинг: 0 / 0
18.03.2005, 03:10
| Ответить | Цитировать | Написать  
Алгоритм
    #32967220
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
если не известно, фальшивая легче или тяжеле - то вариантов - 24

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

разбиваем оставшихся 12 монет на 3 группы.
в группах фиксируем порядок.
группы располагаем по кругу

Код: plaintext
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.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
                            остаток

       левая_чашка_весов           правая_шачка_весов

вводим две операции:
 1 )
  ИП- операция изменения порядка монет в группе: вторая монета переходит на нулевое место.

 2 )
  CМ-
 операция смены монет между группами:
   против часой стрелке передаем 2ю и 3ю монету как  0  и  1  в группе справа
   по часовой стрелке   передаем 0ю монету      как  3   в группе слева

 3 ) 
 применяем ко всем группам ИП и СМ два раза




 4 )
  начальное состояние
  случайно (-)))))))))))))))))))))))) оказалось такое 

                CFTN       
     DOAM                ELIK         

после применения ИП


                 TCFN
     ADOM                IELK         //   ma do   like                первое взвешивание


после применения  CМ

                 LKCA
       FNDI              OMET          //  find me to           второе взвешивание
----------->

после применения ИП

                CLKA
       DFNI              EOMT

после применения СМ

                 MTLD
       KAFE               NIOC        // fake coin                третье взвешивание


 5 )
почему преобразования ИП+СМ дает  24  неповторяющихся различных комбинации для каждой 
монеты ума не приложу. -((((((((

фальши    результат взвешивания
вая мо      при условии, что
нета     фальшивая     фальшивая 
         легче         тяжелее
 
f +>     oo лт  лт     оо тл   тл
...
t +>     оо тл  оо     оо лт   оо


 6 )
похоже на группу преобразования лоренца-пуанкаре (шутка)
...
Рейтинг: 0 / 0
18.03.2005, 06:55
| Ответить | Цитировать | Написать  
Алгоритм
    #32967224
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
2 Федя
с головоломками ходи в вопрос ответ,
а сюда - с алгоритмами.
...
Рейтинг: 0 / 0
18.03.2005, 06:58
| Ответить | Цитировать | Написать  
Алгоритм
    #32967922
Уртьев Федя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Уртьев Федя
Гость
tchingiz2 Федя
с головоломками ходи в вопрос ответ,
а сюда - с алгоритмами.

Хорошо - вот с алгоритмами: есть 2^n бокалов вина, один из них отравлен.
Есть устоойство - опускаешь в бокал, а оно говорит - отравлено или нет.
Найти отравленный бокал за n шагов.
...
Рейтинг: 0 / 0
18.03.2005, 12:37
| Ответить | Цитировать | Написать  
Алгоритм
    #32969335
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
Хорошо - вот с алгоритмами: есть 2^n бокалов вина, один из них отравлен.
Есть устоойство - опускаешь в бокал, а оно говорит - отравлено или нет.
Найти отравленный бокал за n шагов.

Если устройство очень чувствительное( способно яд по капле распознать) то просто нужна свободная рюмка..

отливаем из половины бокалов по капле туда..
суем ентот термометр - если все в порядке - выпиваем...
если не - угощаем когонить..

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

если n не очень большое то сумея устоять на ногах к концу эксперимента
найдем енту отравленую гадость.. как раз гдето за n шагов
...
Рейтинг: 0 / 0
18.03.2005, 23:10
| Ответить | Цитировать | Написать  
Алгоритм
    #32969350
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
Федя
1
давай сначала доказательство, что выписанная выше процедура смены
монет дает решение.
2
давай доказательство, что эту процедуру нельзя упростить.

ну, например, до такой нельзя упростить:
после каждого взвешивания смещать монеты по одной по часовой стрелке.
то есть 0 монета в одной пред.группе становится 3 монетой в след. группе.

очевидно, что такое изменение не работает в случае, если фальшивая монета лежит на 2 или 3 позиции в любой группе - нет возможности за 3 взвешивания
их отличить. результаты всегда будут одинаковые для обоих монет.
...
Рейтинг: 0 / 0
18.03.2005, 23:57
| Ответить | Цитировать | Написать  
21 сообщений из 21, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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