С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
#1

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

23.06.2013, 00:09. Просмотров 528. Ответов 8
Метки нет (Все метки)

Здравствуйте! Возникли некоторые вопросы по дихотомии, а конкретнее, как её применить для решения парочки задач.

Имеется 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 минуты
я вроде бы и знаю, что такое бинарный поиск, и бин поиск по овтету.И корни извлекал из числа при помощи дихотомии, но это решить никак не получается
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.06.2013, 00:09
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задачи на дихотомию (C++):

Отмена задачи, запуск задачи после отмены, перезапуск уже запущенной задачи - C#
Добрый день. Сейчас разбираю TPL и у меня возник вопрос следующего содержания: у меня есть пример на Windows Forms с запуском и отменой...

Задачи задачи решаемость, а как решать ? - Электричество и магнетизм
1. Линейная плотность заряда бесконечно длинного тонкого провода равна \tau = 15 нКл/м. Найти разность потенциалов \Delta \varphi между...

Транспортные задачи и задачи о назначениях и отбор - MS Excel
Помогите разобраться. Задание на сайте http://www.hcxl.ru/bookQMM02.html. Задача 2.П-1. Дорстрой и 2.П-2. Поставки двух видов...

Антон решает задачи. Подскажите Антону, в каком порядке нужно решать задачи, чтобы на выполнение всей работы ушло как можно меньше времени - Pascal ABC
Пожалуйста помогите с задачей Мальчик Антон решает вступительную работу в летний математический лагерь. В ней N заданий, которые можно...

Задачи вида "Развилка" (Текстовые задачи) - QBasic
Здравствуйте, пожалуйста помогите написать проги в QBasic по решению задач: Задача №1 Даны два угла треугольника (в градусах)....

Отмена задачи, запуск задачи после отмены, перезапуск уже запущенной задачи - C#
Добрый день. Сейчас разбираю TPL и у меня возник вопрос следующего содержания: у меня есть пример на Windows Forms с запуском и отменой...

Задачи задачи решаемость, а как решать ? - Электричество и магнетизм
1. Линейная плотность заряда бесконечно длинного тонкого провода равна \tau = 15 нКл/м. Найти разность потенциалов \Delta \varphi между...

Транспортные задачи и задачи о назначениях и отбор - MS Excel
Помогите разобраться. Задание на сайте http://www.hcxl.ru/bookQMM02.html. Задача 2.П-1. Дорстрой и 2.П-2. Поставки двух видов...

Антон решает задачи. Подскажите Антону, в каком порядке нужно решать задачи, чтобы на выполнение всей работы ушло как можно меньше времени - Pascal ABC
Пожалуйста помогите с задачей Мальчик Антон решает вступительную работу в летний математический лагерь. В ней N заданий, которые можно...

Задачи вида "Развилка" (Текстовые задачи) - QBasic
Здравствуйте, пожалуйста помогите написать проги в QBasic по решению задач: Задача №1 Даны два угла треугольника (в градусах)....

Отмена задачи, запуск задачи после отмены, перезапуск уже запущенной задачи - C#
Добрый день. Сейчас разбираю TPL и у меня возник вопрос следующего содержания: у меня есть пример на Windows Forms с запуском и отменой...

Задачи задачи решаемость, а как решать ? - Электричество и магнетизм
1. Линейная плотность заряда бесконечно длинного тонкого провода равна \tau = 15 нКл/м. Найти разность потенциалов \Delta \varphi между...

Транспортные задачи и задачи о назначениях и отбор - MS Excel<

Отмена задачи, запуск задачи после отмены, перезапуск уже запущенной задачи - C#
Добрый день. Сейчас разбираю TPL и у меня возник вопрос следующего содержания: у меня есть пример на Windows Forms с запуском и отменой...

Задачи задачи решаемость, а как решать ? - Электричество и магнетизм
1. Линейная плотность заряда бесконечно длинного тонкого провода равна \tau = 15 нКл/м. Найти разность потенциалов \Delta \varphi между...

Транспортные задачи и задачи о назначениях и отбор - MS Excel
Помогите разобраться. Задание на сайте http://www.hcxl.ru/bookQMM02.html. Задача 2.П-1. Дорстрой и 2.П-2. Поставки двух видов...

Антон решает задачи. Подскажите Антону, в каком порядке нужно решать задачи, чтобы на выполнение всей работы ушло как можно меньше времени - Pascal ABC
Пожалуйста помогите с задачей Мальчик Антон решает вступительную работу в летний математический лагерь. В ней N заданий, которые можно...

Задачи вида "Развилка" (Текстовые задачи) - QBasic
Здравствуйте, пожалуйста помогите написать проги в QBasic по решению задач: Задача №1 Даны два угла треугольника (в градусах)....


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

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

Добавлено через 4 минуты
@MrGluck, а меня смущает, что там сказано, что разница прямо пропорциональна массе, а у вас получается, что разница между всеми днями будет одинакова
0
MrGluck
Модератор
Эксперт CЭксперт С++
7498 / 4614 / 694
Регистрация: 29.11.2010
Сообщений: 12,634
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}}}
1
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
23.06.2013, 02:25  [ТС] #5
О, это уже больше на правду похоже)Вот тут они и хотят видно, чтобы дихотомию применяли(нахождение корня 20 степени).Но мы не дураки, мы просто в степень возведем=)Спасибо большое

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

Если прямоугольник можно ложить только сторонами паралельно сторонам, то это очень легко.Но про это не сказано ни слова.Да к тому же, задача олимпиадная, значит 2-ой прямоугольник можно поворачивать произвольно.Вот тут у меня и проблема.И да, эта задача тоже на дихотомию=))
0
MrGluck
Модератор
Эксперт CЭксперт С++
7498 / 4614 / 694
Регистрация: 29.11.2010
Сообщений: 12,634
23.06.2013, 02:58 #8
@ZaMaZaN4iK,

Не по теме:

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.