Решение и описание Алгоритма - вопрос №473188

В предложенных задачах требуется дать словесное описание алгоритма решения предложенной задачи (если не оговаривается что-то другое). При проверке решений (алгоритмов) будут учитываться следующие параметры: а) четкость описания алгоритма, б) результативность (алгоритм в любом случае должен давать некоторый результат), в) корректность (алгоритм должен давать правильный ответ при любых корректных входных данных), г) оптимальность (следует привести по возможности наиболее оптимальный по количествушагов алгоритм; из нескольких корректных алгоритмов больше баллов получит наиболее оптимальный). 1. Конверты По краю очень большого круглого стола с равными интервалами разложены небольшие конверты, в каждом из которых лежат деньги. Известны суммы, лежащие в каждом конверте. Опишите алгоритм, позволяющий провести прямую через центр стола, разделяющую конверты на два множества с одинаковой суммой денег. Прямая не должна проходить по конвертам. Если такой прямой нет – сообщите об этом. 2. Алгоритм Функция S, аргументами которой являются два действительных числа, задана следующей блок-схемой: Какое значение примет переменная w после выполнения следующих команд: а) w := S(3, 4); б) w := S(1, 3)? 3. Преобразования числа С написанным на доске числом производят следующее действие. Каждую его цифру возводят в квадрат, все результаты суммируют и результат выписывают на доску вместо исходного числа. Так продолжается сколько угодно раз. Опишите алгоритм, определяющий, можно ли таким образом получить из начального натурального числа N заданное натуральное число M? Обоснуйте конечность разработанного алгоритма. 4. Найдите карточку На столе в виде прямоугольника N×M лежат карточки, на которых написаны числа. Карточки лежат числами вниз. Известно, что в каждой строке числа упорядочены по возрастанию слева направо и в каждом столбце числа упорядочены по возрастанию сверху вниз. Задаётся число X. За возможно меньшее количество переворачиваний карточек требуется найти карточку с числом X или заявить, что такой карточки на столе нет. Решите задачу в двух случаях: а) N=10, M=10; б) N=4, M=17. 5. Двоичные числа по кругу Заданы натуральные N и K. Требуется расположить по кругу все N-разрядные двоичные числа, в записи которых содержится ровно K единиц, чтобы соседние числа различались только в двух разрядах. Ведущие разряды двоичного числа могут быть нулевыми. Например при N=4 и K=2 числа можно расположить так: 1100 1010 1001 0101 0011 0110 Опишите алгоритм, как это можно сделать при произвольных N и K.

Лучший ответ по мнению автора

Задачи олимпиадные?

1) Решается перебором А от 1 до Н/2-1 если число четное — получаем 2  отрезка — от А до Н/2+А и от Н/2+А+1 до А-1. Сравниваем эти сумы. 

Если Н нечетное — проверяем 2 случая:

  от А до (Н-1)/2+А и от (Н+1)/2+А+1 до А-1.  (по кругу)

  от А до (Н+1)/2+А и от (Н+3)/2+А до А-1. 

 Если нашли равные сумы -стоп, результат есть.

Если перебрали все и не нашли —   такой прямой нет.

2) Не все условие, нет рисунка

3) Если рассмотреть указанное преобразование, можно сделать вывод, что для чисел больших 99 результат будет меньше исходного числа. После нескольких преобразований получим максимум трехзначное число. Количество таких натуральных чисел — 999. Таким образом значения функции будут повторяться (зацикливание). Таким образом последовательное применение преобразования приведет или к нужному результату, или к зацикливанию. Для проверки зацикливания достаточно отслеживать числа от 1 до 999. Если заданное число М больше 99 — зацикливание можно и не проверять — если результат преобразования стал меньше М — все, искомое число получить нельзя.

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

4)  Сначала делаем бинарный поиск по концам строк (или столбцов, если их меньше), и проверяем, попадает ли искомое число между ними. Если да — проверяем строки (или столбцы), применяя бинарный поиск. Если нашли Х — все. Перебрали все, но не нашли Х — его там нет. Алгоритм, возможно, не оптимальный.

5)  ? Пока не придумал

 

 

 

25.11.12
Лучший ответ по мнению автора

Еva

Читать ответы

1 1

Читать ответы
Посмотреть всех экспертов из раздела Учеба и наука > Информатика
Пользуйтесь нашим приложением Доступно на Google Play Загрузите в App Store