Форум программистов, компьютерный форум CyberForum.ru

Задачи на дихотомию - C++

Восстановить пароль Регистрация
 
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
23.06.2013, 00:09     Задачи на дихотомию #1
Здравствуйте! Возникли некоторые вопросы по дихотомии, а конкретнее, как её применить для решения парочки задач.

Имеется 2 задачи:
1)Курс лечебного голодания длился 21 день. В результате ежедневного взвешивания пациента были получены результаты m(1),...,m(21). Оказалось, что изменение веса между i-тым и i+1-ым взвешиваниями, i=1,...,20, прямо пропорционально весу в i-тый день m(i).

Вводятся веса m(1) и m(21). Необходимо найти m(2) - вес человека во 2-ой день. Ответ вывести с 4 цифрами после запятой.

2)Математическая постановка задачи сводится к следующему:
Во входном файле задается количество тестов T и для каждого теста размеры двух прямоугольников (A1,B1) и (A2,B2). Требуется выяснить, возможно ли разместить второй прямоугольник внутри первого, причем так, чтобы ни одна из его вершин не лежала на сторонах внешнего прямоугольника. Если возможно - то выводить фразу "Escape is possible." Иначе - "Box cannot be dropped."


Их надо как-то решить с помощью дихотомии.Но я, если честно, даже не представляю, как это сделать.

Если можно, то помогите.И будет очень хорошо, если подробно обьясните.

Заранее спасибо!

Добавлено через 2 часа 22 минуты
я вроде бы и знаю, что такое бинарный поиск, и бин поиск по овтету.И корни извлекал из числа при помощи дихотомии, но это решить никак не получается
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.06.2013, 00:09     Задачи на дихотомию
Посмотрите здесь:

C++ Задачи на С++
Задачи в VS C++ C++
3 задачи по С++ C++
задачи по С++ C++
C++ Задачи
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,428
23.06.2013, 01:50     Задачи на дихотомию #2
Ума не приложу, при чем здесь дихотомия в первой задаче. По-моему, ответ должен быть таким:
http://www.cyberforum.ru/cgi-bin/latex.cgi?{m}_{2} = {m}_{1} + \frac{{m}_{21} - {m}_{1}}{20}
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
23.06.2013, 02:07  [ТС]     Задачи на дихотомию #3
@MrGluck, а я вообще не представляю как её решить.Да к тому же, как туда дихотомию прикрутить, вообще не поддается моему разуму

Добавлено через 4 минуты
@MrGluck, а меня смущает, что там сказано, что разница прямо пропорциональна массе, а у вас получается, что разница между всеми днями будет одинакова
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,428
23.06.2013, 02:16     Задачи на дихотомию #4
@ZaMaZaN4iK, действительно. Тогда так:
http://www.cyberforum.ru/cgi-bin/latex.cgi?{m}_{2} = {m}_{1} * k
http://www.cyberforum.ru/cgi-bin/latex.cgi?{m}_{3} = {m}_{2} * k = {m}_{1} * {k}^{2}
...
http://www.cyberforum.ru/cgi-bin/latex.cgi?{m}_{21} = {m}_{1} * {k}^{20}
http://www.cyberforum.ru/cgi-bin/latex.cgi?{k}^{20} = \frac{{m}_{21}}{{m}_{1}}
http://www.cyberforum.ru/cgi-bin/latex.cgi?{m}_{2} = {m}_{1} * k = {m}_{1} *http://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt[20]{\frac{{m}_{21}}{{m}_{1}}}
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
23.06.2013, 02:25  [ТС]     Задачи на дихотомию #5
О, это уже больше на правду похоже)Вот тут они и хотят видно, чтобы дихотомию применяли(нахождение корня 20 степени).Но мы не дураки, мы просто в степень возведем=)Спасибо большое

Добавлено через 1 минуту
А насчёт второй задачи у Вас мысли есть?
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,428
23.06.2013, 02:29     Задачи на дихотомию #6
Я не до конца понял условия. Что за тесты? И как они соотносятся между собой? И что в итоге надо выяснить? По каждому тесту то ответ написать не проблема, но четкой постановки задачи не было и, скорее всего, требуется не это, а какой-то один ответ.
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
23.06.2013, 02:39  [ТС]     Задачи на дихотомию #7
А сам потом перевёл с англиского - математическая модель верна.Тут даны размеры сторон 1-ого прямоугольника, а потом размеры сторон 2-ого прямоугольника.И спрашивается - возможно ли разместить 2-ой прямоугольник внутри 1-ого.При чём он должен строго вмещаться, то есть касания сторон быть не может.

Если прямоугольник можно ложить только сторонами паралельно сторонам, то это очень легко.Но про это не сказано ни слова.Да к тому же, задача олимпиадная, значит 2-ой прямоугольник можно поворачивать произвольно.Вот тут у меня и проблема.И да, эта задача тоже на дихотомию=))
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,428
23.06.2013, 02:58     Задачи на дихотомию #8
@ZaMaZaN4iK,

Не по теме:

широкую на широкую

Внимание, содержит нецензурную лексику


Не понимаю, при чем здесь дихотомия. Просто проверить, влезает ли один прямоугольник у другой: широкую на широкую(большую длину с большей, меньшую с меньшей), далее проверить по диагонали если класть и вроде бы все. Непонятно, при чем здесь тесты?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.06.2013, 03:03     Задачи на дихотомию
Еще ссылки по теме:

C++ Задачи С++
C++ 4 задачи на С++
C++ задачи по С++

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

Или воспользуйтесь поиском по форуму:
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
23.06.2013, 03:03  [ТС]     Задачи на дихотомию #9
А, извините, что про тесты не ответил.А это просто сколько прямоугольников нужно сравнить=) Например:
2
10 10 8 8
8 8 10 10

Добавлено через 37 секунд
Это так назвали просто - тесты.Я бы назвал кол-во пар прямоугольников для сравнения
Yandex
Объявления
23.06.2013, 03:03     Задачи на дихотомию
Ответ Создать тему
Опции темы

Текущее время: 19:28. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru