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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
Rustam
12 / 12 / 3
Регистрация: 05.09.2009
Сообщений: 440
#1

Пять задач, включая задачу как обезвредить бомбу - C++

05.09.2009, 19:30. Просмотров 1920. Ответов 24
Метки нет (Все метки)

Задача N1

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


Задача N2

Человек вводит 10 чисел, замените 3 максимальным а 7 минимальным.
пример входных данных:
10,20,30,40,50,60,55,45,35,25;
пример выходных данных:
10,20,60,40,50,60,10,45,35,25;


Задача N3

"Осадки"
Вам даётсья задача зделать программу, которая работает с двумя текстовыми файламы (osadki.dat и osadki.rez) и делает при этом несколько вычислений. В 1. файл записаваетсья несколько строк. Первая строка содержит количество дней N, после которой следует количество строк (N). Начиная со второй строки в каждой записано два числа (отделены между собой пробелои) - температура воздуха и количество (в мм) осадков в день. Принимая во внимание, что
1) N <= 1000000
2) количество осадков не меньше 0 и не боль ше 100 мм
3) температура воздуха была между -50 и 50 градусами
4) если Температура меньше нуля падал снег,а во стольных случайах лил дождь
в файле osadki.rez надо вывести два числа отделённых между собой побелами - общая количество снега за все дни и общее количество дождя.
Пример
osadki.dat
3
-1 30
0 3
20 15

osadki.rez
30 18


Задача N4

Ученые астрономы, сообщили правительство, что ровно через T секунд на
планете Олимпиада начнется метеоритный дождь. Правительство планеты срочно
начало эвакуацию людей и
важного оборудования - телескопических установок.
Для защиты телескопу его нужно транспортировать в специально отведенное
место - хранилище. В одном хранилище может вместиться лишь один телескоп.
Необходимо рассчитать максимальное количество телескопов которые можно
успеть спрятать к началу метеоритного дождя.

Входные данные (файл METEOR.DAT):
В первой строке число T - количество секунд через которую метеориты
упадут на планету.
Во второй строке число N - количество телескопов.
В третьей строке находится 2*N чисел - координаты телескопов (x, в)
В четвертой строке число M - количество хранилищ.
В пятой строке находится 2*M чисел - координаты хранилищ (x, в)
В шестой строке число V - скорость транспортировки телескопов.

Примечание:
0<T<1000000 ; 0<N,M<100 ; -30000 <= x,y <=30000 ; 0<V<1000
T, N, M, x, в - цели.

Выходные даны: (файл METEOR.SOL):
В единственную строку файла записать максимальное количество телескопов,
которые могут быть спрятанные к началу падения метеоритов.
Пример METEOR.DAT:
10
4
1 7 3 7 5 7 100 100
2
2 7 4 7
0.1

Пример METEOR.SOL:
2


Задача N5

Взрывное устройство, которое было заложено неизвестным террористом, имеет N - лампочек, и M - переключателей.
Каждый переключатель изменяет состояние некоторых лампочек на противоположный. Для обезвреживания бомбы, необходимо выключить все лампочки.
Напишите программу, которая спасет мир.

Входные данные: (файл BOMBA.DAT):
В первой строке число N. (0<N<=100)
Во второй строке содержится N чисел, которые помечают состояние каждой лампочки (0 - выключенная, 1 - включенная).
В третьей строке содержится число M. (0<M<=100)
В каждом из следующих M строк содержится число K (количество лампочек состояние которых изменяет данный переключатель) и K чисел - номера соответствующих лампочек.
Выходные даны: (файл BOMBA.SOL):
Если бомбу обезвредить невозможно, запишите в исходный файл "NO" (без кавычек).
Если возможно спасти мир, то в первую строку запишите "YES" (без кавычек), а во вторую строку запишите номера переключателей которые необходимо задействовать.
Пример BOMBA.DAT:
5
0 1 1 0 1
4
3 2 3 4
3 1 4 5
2 4 5
2 2 4


P.S. Заранее большое спасибо, надеюсь, кто знает поможет мне!!!!!!!!!!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
07.09.2009, 18:21     Пять задач, включая задачу как обезвредить бомбу #21
Никак не разрешается - просто перебираются все варианты и все
Значение tel2stor[i] содержит номер хранилища куда поедет i-тый телескоп.
При этом еще есть специальное значение - -1, которое обозначает что i-тый телескоп никуда не поедет.
Но и это еще не все - значение itel обозначает номер последнего установленного телескопа.
То есть массив tel2stor[] всегда рассматривается от 0 до itel включительно.
А дальше просто перебираем все варианты и не допускаем чтобы телескоп с большим номером не занял хранилище, если оно занято телескопом с меньшим номером.

Добавлено через 7 минут
При таком переборе конечно есть дубликаты вариантов.
Можно наверное проверять счетчик доставленных телескопов непосредственно перед ходом назад (back), потому что в этот момент достигнуто наибольшее значение itel для данной цепочки.
Но я проверяю счетчик каждый раз.
Можно еще ускорить проверку счетчика заведением дополнительного массива.
Ведь для данной цепочки значение счетчика при itel и при itel-1 может либо совпадать (когда телескоп c номером itel не смог доехать) или быть больше на 1 (когда телескоп доехал).
То есть для вычисления значения счетчика достаточно сделать всего 1 проверку вместо (itel+1) проверки.
Mozart
39 / 17 / 1
Регистрация: 21.08.2009
Сообщений: 63
07.09.2009, 18:31     Пять задач, включая задачу как обезвредить бомбу #22
Т.е., я так понял, просто перебираются все варианты, и возвращается максимальное количество телескопов которых удалось припрятать в момент прохода перебора?
ЗЫ: а я пытался решить этот вопрос без полного перебора, чуть голову не сломал, но таки допер как его делать, вот только еще не закодил.
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
07.09.2009, 18:38     Пять задач, включая задачу как обезвредить бомбу #23
Да - полный перебор, но не совсем - например два телескопа в одно хранилище не едут.
Я думаю все равно все сведется к почти полному перебору.
Можно например поставить телескопы в одну точку и все хранилища в другую точку.
После чего тебе остается только перебирать кто куда поедет.

Во - мой вариант перебора можно еще сократить.
Если мы заняли все хранилища, то дальше расставлять телескопы нет смысла - нужно делать шаг в сторону - label_free.
Mozart
39 / 17 / 1
Регистрация: 21.08.2009
Сообщений: 63
07.09.2009, 18:48     Пять задач, включая задачу как обезвредить бомбу #24
sqrt( dx*dx+dy+dy ); очепятка я так понимаю.
Да таки получится почти полный перебор. В любом случае придется рассматривать каждое возможное положение телескопа, учитывая занятые позиции. Только я это хотел сделать через задницу Х_х
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.09.2009, 19:44     Пять задач, включая задачу как обезвредить бомбу
Еще ссылки по теме:

Передалайте задачу как можна по проще C++
Подготовка к решению сложных задач и задач олимп.уровня C++
как написать задачу в си C++
C++ Пятью пять - двадцать пять

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

Или воспользуйтесь поиском по форуму:
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
07.09.2009, 19:44     Пять задач, включая задачу как обезвредить бомбу #25
Я понял, что задача симметрична.
Можно с таким же успехом расставлять хранилища в телескопы

Добавлено через 1 минуту
очепятка я так понимаю.
Угу - сосредоточился на переборе и не заметил
Кстати для теста ответ совпал
Yandex
Объявления
07.09.2009, 19:44     Пять задач, включая задачу как обезвредить бомбу
Ответ Создать тему
Опции темы

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