Вопрос № 142874: Здравствуйте, помогите, а то я затрудняюсь В библиотеке, которую вы используете, есть строковый класс String. Вы пишете функцию для создания пробельной строки. К сожалению, класс String обладает неудобным интерфейсом и вам приходится написать след...Вопрос № 142875: Помогите, а то я затрудняюсь: Дано квадратное поле из черных и белых клеток в произвольном порядке. Белым прямоугольником называется прямоугольная область,
которая содержит только белые клетки. Максимальным белым прямоугольником называется любой б...Вопрос № 142952: Только познакомился с Visual Studio 2005 Код на Си++. Где получить ехе-шник? В файле проекта нет. Подскажите....
Вопрос № 142.874
Здравствуйте, помогите, а то я затрудняюсь В библиотеке, которую вы используете, есть строковый класс String. Вы пишете функцию для создания пробельной строки. К сожалению, класс String обладает неудобным интерфейсом и вам приходится написать следующий код:
String spaces(int n) { String s; for (int i = 0; i < n; ++i) s = s + ' '; return s; }
Если вы вызовете эту функцию для создания строки из миллиона пробелов, то время ее работы окажется чрезмерно
большим. Сколько времени работает функция spaces? Напишите как можно более быструю функцию spaces, не меняя класса String. Этот класс снабжен операциями + (конкатенация), = (присвоение), литералами “” (пустая строка) и ‘ ‘ (один пробел). Сколько времени будет работать быстрая функция spaces? Напишите и протестируйте быстрый вариант функции spaces. Первоначальный вариант в приложении.
Отвечает: Verena
Здравствуйте, Капранов Павел Павлович! Можно изначально создать достаточно большую строку (либо на фиксированное число пробелов, либо на некое число, получаемое анализом числа n) и наращивать строку результирующую сразу на много пробелов. Допустим, вот так:
Код:
String spaces(int n)
{ String s, q; if (n>100) { for (int i = 0; i < 100; ++i) s = s + ' '; for (int i=0; i < (int)(n/100); i++) q = q+s; } for (int i=0; i< n%100; i++) q=q+' '; return q; }
Скорость для Вашего примера возросла где-то в 4 раза. Можно проанализировать разрядность n и взять за изначальную строку длины половины разрядности или, например, четверти (т.е., допустим, для 10000
00 это можнт быть строка, например, из 1000 пробелов). Так что можете ещё поэкмпериментировать. Удачи!
--------- Эта история - не для истории, понимаешь?
Ответ отправила: Verena (статус: Практикант)
Ответ отправлен: 02.09.2008, 15:01
Вопрос № 142.875
Помогите, а то я затрудняюсь: Дано квадратное поле из черных и белых клеток в произвольном порядке. Белым прямоугольником называется прямоугольная область, которая содержит только белые клетки. Максимальным белым прямоугольником называется любой белый прямоугольник максимальной площади. Предложите алгоритм, который находит максимальный белый прямоугольник. Сколько времени он работает? Можно ли быстрее? Приведите оценку снизу для сложности алгоритма. Напишите программу, которая быстро решает
задачу. Программа, которая решает эту задачу медленно в приложении.
Отвечает: Lang21
Здравствуйте, Капранов Павел Павлович!
Решить задачу можно, используя следующий алгоритм. Кратко суть его в следующем. Заметим, что если внутри прямоугольника есть одна чёрная клетка, то, чтобы найти максимальный белый прямоугольник, нужно сравнить площади 4-х прямоугольников: сверху, снизу, справа и слева от этой клетки. Ещё одна чёрная клетка может попасть в какие-то из этих четырёх прямоугольников. Внутри каждого из них нужно также сравнить площади 4-х прямоугольников. Добавляя на каждом
шаге по одной чёрной клетке и сравнивая 4 прямоугольника, образующиеся внутри ранее найденных, можно получить решение задачи. Проще всего это сделать с помощью рекурсии. Глубина рекурсии составит не более 4^k, k - количество чёрных клеток. Код в приложении. Остальные вопросы можно обсудить в минифоруме.
Приложение:
Ответ отправил: Lang21 (статус: Студент)
Ответ отправлен: 04.09.2008, 19:07
Вопрос № 142.952
Только познакомился с Visual Studio 2005 Код на Си++. Где получить ехе-шник? В файле проекта нет. Подскажите.
Отправлен: 02.09.2008, 23:11
Вопрос задал: Warobushek (статус: 1-ый класс)
Всего ответов: 1 Мини-форум вопроса >>> (сообщений: 3)
Отвечает: Макс Коваленко Юрьевич
Здравствуйте, Warobushek! Options-> Directories -> executable - получаете путь. Но по умолчанию exe сохраняется в папке с проэктом. хорошо проверьте. должен быть. желаю успехов =)
Ответ отправил: Макс Коваленко Юрьевич (статус: 1-ый класс)
Ответ отправлен: 02.09.2008, 23:22 Оценка за ответ: 5