Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.80/40: Рейтинг темы: голосов - 40, средняя оценка - 4.80
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32

Найти фальшивую монету за заданное количество взвешиваний

26.06.2016, 01:53. Показов 8249. Ответов 22
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Недавно узнал про эту известную задачку, написал тестовую кату на одном сайте компьютерных задачек (на Haskell), теперь хотел бы предложить желающим решить ее на С++. Имхо интересно ее решить самостоятельно, без читерства.

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

Я накидал простейшую тестирующую систему на С++ в процедурном стиле, требуется написать одну недостающую функцию - собственно определяющую номер фальшивой монеты (от 1 до количества монет) по заданному количеству взвешиваний и монет. Реализована функция взвешивания - она принимает два множества (номера монет на левую и на правую чашу весов) и возвращает значение, подробно описанное в комментариях в коде. Служебные глобальные переменные писать/читать нельзя - в проверочных тестах я их переименую. Собственно, все Если есть вопросы - готов ответить.
C++
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <set>
#include <algorithm>
 
// функция, которую требуется написать - возвращает номер фальшивой монеты (от 1 до coins)
 
int getFalseCoin (
    const int weighings, // количество взвешиваний
    const int coins      // количество монет
);
 
// недоступные переменные - в реальных тестах переименую чтобы не было читерства :)
 
int  falseCoinNumber;    // номер фальшивой монеты при тестах
bool falseCoinIsHeavier; // фальшивая монета тяжелее/легче
int  weighingActs;       // максимальное количество взвешиваний на 1 тест
 
// функция взвешивания, которой можно пользоваться при реализации getFalseCoin
 
enum WeighingRezult {
    LT,    // левая чаша легче
    GT,    // левая чаша тяжелее
    EQ,    // весы уравновешены
    UNDEF  // взвешивание некорректно
};
 
typedef std::set<int>& sr_t;
 
WeighingRezult weighing (sr_t l, sr_t r) {
    if (weighingActs-- <= 0) return UNDEF; // если взвешивания кончились, возвращаем UNDEF
    
    std::set<int> is;
    std::set_intersection(l.begin(), l.end(), r.begin(), r.end(), std::inserter(is, is.begin()));
    
    if (!is.empty()) return UNDEF; // если есть дубли монет на чашах, возвращаем UNDEF
    else if (l.size() < r.size()) return LT;
    else if (l.size() > r.size()) return GT;
    else if (l.find(falseCoinNumber) != l.end()) return falseCoinIsHeavier ? GT : LT;
    else if (r.find(falseCoinNumber) != r.end()) return falseCoinIsHeavier ? LT : GT;
    else return EQ;
}
 
// функция тестирует getFalseCoin при заданной фальшивой монете
// для 2-х случаев: фальшивая монета тяжелее и фальшивая монета легче настоящей
 
bool testOneCoin (const int weighings, const int coins, const int fc) {
    falseCoinNumber = fc;
    
    weighingActs = weighings;
    falseCoinIsHeavier = true;
    bool t1 = getFalseCoin(weighings, coins) == falseCoinNumber;
    
    weighingActs = weighings;    
    falseCoinIsHeavier = false;
    bool t2 = getFalseCoin(weighings, coins) == falseCoinNumber;
    
    return t1 && t2;
}
 
// функция тестирует testOneCoin для каждого номера фальшивой монеты от 1 до coins
 
bool testAllCoins (const int weighings, const int coins) {
    bool r = true;
    for(int i=1; i<=coins; i++) r&=testOneCoin(weighings, coins, i);
    return r;
}
 
// функция тестирует testAllCoins для интервала количества монет coins
 
bool testInterval (const int weighings, const int coinsFrom, const int coinsTo) {
    bool r = true;
    for(int i=coinsFrom; i<=coinsTo; i++) r&=testAllCoins(weighings, i);
    return r;
}
 
int main() {
    std::cout << testAllCoins (2, 4) << '\n';
    std::cout << testInterval (3, 3, 13) << '\n';
    std::cout << testInterval (4, 3, 40) << '\n';
    std::cout << testInterval (5, 3, 121) << '\n';
    std::cout << testInterval (6, 360, 364) << '\n';
}
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
26.06.2016, 01:53
Ответы с готовыми решениями:

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

За какое наименьшее количество взвешиваний можно обнаружить фальшивую монету?
Среди N монет существует одна фальшивая, которая легче других. Остальные имеют одинаковый вес. Есть обычные весы на две чаши. Необходимо...

Определить фальшивую монету за заданое число взвешиваний среди указанного количества золотых монет
Есть 25 золотых монет. Одна из них фальшивая и она по весу меньше. Определить за 3 взвешивания фальшивую монету. Взвешивание производится...

22
Модератор
Эксперт по электронике
8982 / 6749 / 921
Регистрация: 14.02.2011
Сообщений: 23,878
04.08.2016, 00:42
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от _Ivana Посмотреть сообщение
пишите код решения,
прежде чем код писать, нужно в голове решить, а с этим у меня затык
Цитата Сообщение от _Ivana Посмотреть сообщение
Или вам все-таки интересно подумать самому?
Подумать самому оно конечно интересней но боюсь из-за текучки заброшу эту задачу
сделаем так, если не смогу решить тогда попрошу подсказку
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
04.08.2016, 00:45  [ТС]
Цитата Сообщение от ValeryS Посмотреть сообщение
сделаем так, если не смогу решить тогда попрошу подсказку
хорошо, я подумаю как вам подсказать, чтобы оставалось еще над чем подумать, но только в личку - вдруг кто еще захочет решить и подумать (хотя вряд ли конечно ). А пока подсказка одна: это возможно - "проверено электроникой"
0
 Аватар для Fulcrum_013
2083 / 1576 / 169
Регистрация: 14.12.2014
Сообщений: 13,614
04.08.2016, 01:19
Цитата Сообщение от Renji Посмотреть сообщение
Разбиваем монеты на три равные кучки А, Б и В.
А если количество монет на 3 не делится?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
04.08.2016, 01:19

За какое минимальное количество взвешиваний можно найти фальшивую монету
Из 4 монет одна фальшивая(неизвестно больше или меньше). За какое минимальное количество взвешиваний её можно найти?

Найти фальшивую монету
Имеется 11 монет. Золотые все. Николаевские червонцы. Среди них одна фальшивая, позолоченная. А внутри свинец. Из химии известно, что...

Надо за 4 взвешивания найти фальшивую монету
Если кому эта задачка покажется излишне простой, то просто скажите что знаете решение, не обязательно его озвучивать - вдруг найдутся те...

Определить фальшивую монету
Все привет, я новенький в программировании И вот мой учитель задал мне домашнее задания на C#, я не могу представить как написать код...

Определить за 3 взвешивания фальшивую монету
Есть 25 золотых монет. Одна из них фальшивая и она по весу меньше. Определить за 3 взвешивания фальшивую монету. Взвешивание производится...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
23
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru