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

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

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

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

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

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

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

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

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

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

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

(1 2 3 4 ..n)

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

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

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


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

два взвешивания явно мало - будет 9 последовательностей.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.03.2005, 03:10
    #32967164
tchingiz
tchingizПривилегированный пользователь
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
oo - одинаково одинаково
лт - легче тяжелее
тл - тяжелее легче
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.03.2005, 06:55
    #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:58
    #32967224
tchingiz
tchingizПривилегированный пользователь
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
2 Федя
с головоломками ходи в вопрос ответ,
а сюда - с алгоритмами.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.03.2005, 12:37
    #32967922
Уртьев Федя
Уртьев Федя
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
tchingiz2 Федя
с головоломками ходи в вопрос ответ,
а сюда - с алгоритмами.

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

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

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

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

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

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

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


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