Доброе утро масакам !!!

← →
gn (2003-08-18 06:30) [0]

Сегодня понедельник, день тежолый и что бы не накосячить в работе предлогаю поднапречь(ну или можно скозать разогреть)мозги для начавшейся трудовой недели.:-)

gn
cn 1101

← →
gn (2003-08-18 06:32) [1]

Задача 1

Вводится последовательность, состоящая из N пар символов (ai,bi). Каждая пара определяет порядок предшествования символов, например, пара (b,с) означает, что символ "b" предшествует символу "с". Из порядка (b,с) и (с,a) следует порядок (b,a). Необходимо определить, является ли введенная последовательность:

а) полной, т.е. все использованные для формирования пар символы (выбросив повторяющиеся) можно выстроить в цепочку (A1,A2,...,As) в порядке предшествования;

б) противоречивой, т.е. для некоторых символов x,y можно

получить одновременно порядок как (x,y) так и (y,x);

Задача 2.

Вокруг считающего стоит N человек, из которых выделен первый, а остальные занумерованы по часовой стрелке числами от 2 до N. Считающий, начиная с кого-то, ведет счет до M. Человек на котором остановился счет, выходит из круга. Счет продолжается со следующего человека и так до тех пор, пока не останется один человек.

Определить

a) номер оставшегося человека, если известно M и то, что счет начинался с первого человека;

b) номер человека c которого начинался счет, если известно M и номер оставшегося человека L.

Задача 3.

Задана полоска длиной 2k клеток и шириной в одну клетку. Полоску сгибают пополам так, чтобы правая половинка оказалась под левой. Сгибание продолжают до тех пор, пока сверху находится больше одной клетки. Необходимо пронумеровать клетки таким образом, чтобы после окончания сгибания полосы номера клеток в получившейся колонке были расположены в порядке 1,2,3,4,...,2k.

gn
cn 1101

← →
gn (2003-08-18 06:33) [2]

Задача 3.1.

"Полоска". Прохоров В.В.

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

- на первом шаге ее согнули пополам так, что верхняя половина легла на нижнюю либо спереди (П - сгибание) либо сзади (З сгибание),

- на последующих n-1 шагах выполняли аналогичное действие с получающейся на предыдущем шаге согнутой ленточкой, как с единым целым.

Затем ленточку развернули , приведя ее в исходное состояние. На ней остались сгибы - ребра от перегибов, причем некоторые из ребер оказались направленными выпуклостью к нам (К - ребра), а некоторые - от нас (О -ребра). Ребра пронумеровали сверху вниз числами от 1 до 2n-1.

А. Составить программу, запрашивающую:

- строку символов из прописных букв "П" и "З", определяющую последовательность типов сгибаний, - номер ребра, и сообщающую тип этого ребра, получившийся после заданной последовательности сгибаний.

Б. Составить программу, запрашивающую строку символов из прописных букв "О" и "К", где нахождение на i-том месте символа "О" или "К" определяет тип ребра на расправленной полоске, и выдающую строку из прописных "П" и "З", определяющих последовательность типов сгибаний, посредством которых получена ленточка с исходной последовательностью ребер. Если такой строки не существует, сообщить об этом.

Задача 4.

Квадрат разбит на 4k равновеликих квадратных клеток. Квадрат перегибается поочередно относительно вертикальной (правая половина подкладывается под левую) и горизонтальной (нижняя половина подкладывается под верхнюю) оси симметрии до тех пор, пока все клетки не будут расположены друг под другом. Требуется занумеровать клетки исходного квадрата таким образом, чтобы в результате выполнения операций перегиба номера клеток, расположенных друг под другом, образовали числовую последовательность 1,2,3,...,4k, начиная с верхней клетки.

Задача 5.

Даны обозначения двух полей шахматной доски (например, A5 и C2). Найти минимальное число ходов, которые нужны шахматному коню для перехода с первого поля на второе.

Задача 6.

Дана конечная последовательность, состоящая из левых и правых скобок pазличных заданных типов. Как определить, можно ли добавить в нее цифры и знаки арифметических действий так, чтобы получилось правильное арифметическое выражение.

Задача 7.

В таблице А размера N за один просмотр необходимо каждый элемент заменить на ближайший следующий за ним элемент, который больше его. Если такого элемента нет, то заменить его на ноль. Можно использовать дополнительную память.

ПРИМЕР А=1 3 2 5 3 4

ОТВЕТ А=3 5 5 0 4 0

gn
cn 1101

← →
gn (2003-08-18 06:33) [3]

Задача 8.

В городе расположены n автобусных остановок, обозначенных числами из N={1,2,....,n}. Имеется R автобусных маршрутов, заданных последовательностями соседних остановок при движении автобуса в одном направлении:

М1={I11,I12,...,I1m1},

М2={I21,I22,...,I2m2},

.....

Mr={Ir1,Ir2,...,Irmr},

где Ijk натуральное.

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

Задача 9.

Одинокий король долго ходил по бесконечной шахматной доске. Известна последовательность из N его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.).Написать программу, определяющую побывал ли король дважды на одном и том же поле за минимально возможное при заданном N число вычислений.

Задача 10

По кругу расположено N монет гербами вверх и M монет гербами вниз. Обходя круг по ходу часовой стрелки, переворачивает каждую S -тую монету. В первый раз счет начинается с герба. В каком порядке надо расставить монеты, чтобы после K ходов стало L монет, лежащих гербами вверх.

Задача 11.

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

Задача 12.

Из листа клетчатой бумаги размером М*N клеток удалили некоторые клетки. На сколько кусков распадется оставшаяся часть листа?

Пример. Если из шахматной доски удалить все клетки одного цвета, то оставшаяся часть распадется на 32 куска.

МОДИФИКАЦИЯ. То же, но перед удалением клеток лист склеили в цилиндр высотой N.

Задача 13.

Имеется n черных и белых карточек, сложенных в стопку. Карточки раскладываются на стол в одну линию следующим образом: первая кладется на стол, вторая под низ стопки, третья- на стол, четвертая - под низ стопки и т.д., пока все карточки не будут выложены на стол. Каким должно быть исходное расположение карточек в стопке, чтобы разложенные на столе карточки чередовались по цвету: белая, черная, белая, черная и т.д.

Задача 14.

Фоpма тела задана матpицей А pазмеpности M x N. Элементы матpицы - натуpальные числа. Элемент А ( i,j ) соответствует высоте гоpизонтальной квадpатной площадки pазмеpа 1 x 1 относительно нижнего основания.Нижнее основание фоpмы горизонтально.

Опpеделить объем невытекшей воды, если

a) Тело опускается полностью в воду, затем поднимается;

После подъема вода останется только во внутреннем углублении, над элементом А(2,2)=1.

Объем воды равен 1.

b) В позицию (i0,j0) выливается объем воды V.

gn
cn 1101

← →
gn (2003-08-18 06:34) [4]

Задача 15.

Матрица размера N*M определяет некоторый лабиринт. B матице элемент 1 обозначает стену, а 0 определяет свободное место. В первой строке матрицы определяются входы x(i), а в последней выходы y(i), i=1,..,k, которые должны быть нулевыми элементами.

Необходимо определить, можно ли

а) провести k человек от входа x(i) до выхода y(i) соответственно, i=1,..,k, таким образом, чтобы каждое свободное место посещалось не более одного раза.

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

Задача 16.

Есть министерство из N чиновников, где N натуральное число. У каждого из чиновников могут быть как подчиненные, так и начальники, причем справедливы правила: подчиненные моего подчиненного мои подчиненные, начальники моего начальника - мои начальники, мой начальник не есть мой подчиненный, у каждого чиновника не более одного непосредственного начальника.

Для того чтобы получить лицензию на вывоз меди необходимо получить подпись 1-ого чиновника - начальника всех чиновников. Проблема осложняется тем, что каждый чиновник, вообще говоря, может потребовать "визы", т.е. подписи некоторых своих непосредственных подчиненных и взятку - известное количество долларов. Для каждого чиновника известен непустой список возможных наборов "виз" и соответствующая каждому набору взятка. Пустой набор означает, что данный чиновник не требует виз в данном случае. Чиновник ставит свою подпись лишь после того, как ему представлены все подписи одного из наборов "виз" и уплачена соответствующая взятка.

Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость.

N<100. Количество наборов для каждого чиновника не превосходит 15.

gn
cn 1101

Доброе утро масакам !!! Найти похожие ветки