Пятничные задачки ;)

← →
MBo © (2006-12-22 14:08) [0]

1. Вася Пупкин построил экспериментальную установку по измерению торсионных
полей. Ротор установки представляет собой диск, который разделен своим диаметром
на черную и белую половины. Оптический датчик устанавливается над диском и выдает код
1 при переходе с черного на белое и 0 при обратном переходе. Какое минимальное
количество датчиков понадобится для определения направления вращения диска,
и как их нужно расположить для наиболее быстрого в среднем определения направления
при начале действия торсионных полей?

2. Вася Пупкин должен отобрать для участия в тараканьих бегах три самых быстрых
насекомых из 25 имеющихся. За какое минимальное число забегов можно это сделать,
если в забеге участвуют 5 тараканов, скорость каждого постоянна от забега к забегу.

3. Массив длиной N содержит только нули и единицы. Как отсортировать массив за ОДИН
проход без использования дополнительной памяти.

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

5. Из пункта А в пункт Б по одной прямой дороге выехали две машины, навстречу им
еще две, все с постоянной скоростью. Встречи произошли на расстоянии от пункта А
3, 4, 6 и 7 километров. Какое же расстояние между пунктами А и Б?

6. Алгоритм Маркова - программа для преобразования одной символьной строки
в другую, записываемая в следующем виде:
1. <substr 1> -> <str 1>
2. <substr 2> -> <str 2>
3. <substr 3> -> <str 3>
.......
n. <substr n> -> <str n>
вместо -> в некоторых строках программы может быть символ |->

Работает так:
исходная строка проверяется на наличие подстроки <substr 1>, если найдено,
то подстрока <substr 1> заменяется на <str 1> (выполнено правило 1),
если нет, то проверяется на наличие <substr 2> и т.д. Если замена произошла,
то полученая строка снова проверяется на наличие <substr 1> и т.д.,
пока не наступит конец программы.

Конец программы наступает если
1) не выполнено ни одно правило
2) выполнено правило с символом |->
Пустая подстрока входит в любую строку
Разрешается использовать любые символы, в том числе и не входящие в исходную
и результирующие строки, пустые строки обозначим {}

Например, имеется строка состоящая из n символов "x", надо написать программу, заменяющую эту строку на строку из 2n символов "x"
программа
1) x->xx
работать не будет, точнее говоря, она никогда не остановится
правильная программа:
1) 1x->xx1
2) x1|->x
3) x->xx1
проверим на примере строки xxx
xxx (3) xx1xx (1) xxxx1x (1) xxxxxx1 (2) xxxxxx
А теперь несколько задачек:

а) Преобразовать строку из n символов x в двоичную запись числа n (например, из xxxxxx должно получиться 110)
б) Преобразовать строку, являющуюся двоичной записью числа n в строку из n символов x (например, из 101 должно получиться xxxxx)
в) Преобразовать строку из символов a и b в строку-перевертыш (например из aababba должно получиться abbabaa)
г) Преобразовать строку из n символов x в строку из n^2 символов y

7. В единичном квадрате случайным образом выбраны 3 точки.
Какова будет средняя площадь полученного треугольника?

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

9. Числа Стирлинга 2 рода определяются так:
S(n,1) = 1
S(n,n) = 1
S(n,k) = S(n-1, k-1) + k*S(n-1,k)
По определению нетрудно составить рекурсивную функцию, но она будет довольно
медленной для значений параметров, скажем, до миллиона. Как более эффективно вычислить S(n,k)?

← →
boriskb © (2006-12-22 14:12) [1]

MBo © (22.12.06 14:08)
Вася Пупкин построил экспериментальную установку

Этот Вася...
Всё ему надо. В каждой бочке затычка.
Интересный должен быть мужик :))

← →
MBo © (2006-12-22 14:18) [2]

Еще одну забыл дописать:

10. Для векторов X и Y известны ненулевая сумма a, скалярное произведение p = (X.Y) и векторное произведение b = [X*Y]
Найти вектора X, Y

← →
MBo © (2006-12-22 14:22) [3]

к 3) задаче: O(1) памяти, конечно, можно использовать.

← →
Ega23 © (2006-12-22 14:30) [4]

2 - уточните, в каждом забеге регистрируется только занятое место, или ещё и время для каждого из тараканов?

← →
MBo © (2006-12-22 14:39) [5]

>2 - уточните, в каждом забеге регистрируется только занятое место
Только место.

← →
Ega23 © (2006-12-22 14:43) [6]

> Только место.

2 - 11 забегов.

← →
jack128 © (2006-12-22 14:44) [7]

MBo © (22.12.06 14:08)
3. Массив длиной N содержит только нули и единицы. Как отсортировать массив за ОДИН
проход без использования дополнительной памяти.

type TDynBooleanArray = array of Integer; procedure SortBooleanArray(var Arr: TDynBooleanArray); var FalseIndex, TrueIndex: Integer; Temp: boolean; begin if Length(Arr) < 2 then Exit; FalseIndex := Low(Arr); TrueIndex := High(Arr); while (FalseIndex < TrueIndex) and not Arr[FalseIndex] do Inc(FalseIndex); while (FalseIndex < TrueIndex) and Arr[TrueIndex] do Dec(TrueIndex); if FalseIndex >= TrueIndex then Exit; // массив отсортирован while FalseIndex < TrueIndex do begin Arr[FalseIndex] := False; Arr[TrueIndex] := True; while (FalseIndex < TrueIndex) and not Arr[FalseIndex] do Inc(FalseIndex); while (FalseIndex < TrueIndex) and Arr[TrueIndex] do Dec(TrueIndex); end; end;

← →
jack128 © (2006-12-22 14:44) [8]

jack128 © (22.12.06 14:44) [7]
TDynBooleanArray = array of boolean;

← →
Alx2 © (2006-12-22 14:44) [9]

Блин, как поздно-то. Мне уже пора уходить :(
3. Два счетчика. Один N0 - сколько нулей, другой N1 - сколько единиц. За проход по массиву сразу получаем сортированную последовательность из N0 нулей и N1 единиц.
Либо пускаем навстречу друг другу два индекса-бегунка пока они не встретятся. Левый стопорится, если в ячейке 1. Правый - если 0. Когда на правом 0, а на левом 1, то меняем местами содержимое ячеек.
Это почти этап partition из QuickSort.

← →
MeF Dei Corvi © (2006-12-22 14:45) [10]

> 3. Массив длиной N содержит только нули и единицы. Как отсортировать
> массив за ОДИНпроход без использования дополнительной памяти.

В ячейку массива можно записать только 1 или 0, или другие числа также допускаются?

← →
DprYg © (2006-12-22 14:52) [11]

> Найти вектора X, Y

А поподробнее? Что значит найти (найти координаты или что)?

← →
MBo © (2006-12-22 15:02) [12]

>MeF Dei Corvi
>В ячейку массива можно записать только 1 или 0, или другие числа также допускаются?
Не допускаются. Даже если можно было бы, подсчет подразумевает не единичный проход по массиву, а это главное ограничение

>DprYg Что значит найти (найти координаты или что)?
выразить через известные a,b,p

← →
Кабан © (2006-12-22 15:18) [13]

7) 1/4

← →
Zeqfreed © (2006-12-22 15:25) [14]

#include <stdio.h> #include <stdlib.h> #include <string.h> int main() { char buf[300]; gets(buf); int swapped = 0; int i = 0; int len = strlen(buf) - 1; int j = len; while (i < len) { if ((buf[i] != "0") && (buf[i] != "1")) { fprintf(stderr, "Invalid input at %d\n", i); exit(1); } if (buf[i] == "1") { while (j > i) { if (buf[j] == "0") { buf[j] = "1"; buf[i] = "0"; break; } j--; } } i++; } printf("Sorted list: %s\n", buf); return 0; }

Это на третью задачу. Вроде условия выполняются, код работает, хотя не могу гарантировать на 100% :) Извиняюсь, что на си.

← →
palva © (2006-12-22 15:30) [15]

2 - Можно за 9.
Сначала разбить по пятеркам это пять забегов. В каждом из них двух отставших можно отбросить.
Потом забег лидеров, после чего двух отставших вместе с их пятерками (уже тройками) можно отбросить.
Оставшиеся девять претендентов участвуют в произвольном порядке в трех забегах, после каждого из них отбрасываем два. Здесь наверно можно как-то сэкономить забеги. Но если не экономить получается 9 забегов.

← →
Ega23 © (2006-12-22 15:37) [16]

Хм.. вроде и вправду 9...

← →
jack128 © (2006-12-22 15:38) [17]

palva © (22.12.06 15:30) [15]
Оставшиеся девять претендентов участвуют в произвольном порядке в трех забегах, после каждого из них отбрасываем два.
как это можно по 2 отбрасывать? Ведь в одном забеге могут участвовать самые быстрые тараканы, а двух других - самые медленные из этих 9ти..

← →
Zeqfreed © (2006-12-22 15:38) [18]

program sort; {$IFNDEF ON_LINUX} {$APPTYPE CONSOLE} {$ENDIF} uses SysUtils; var s : String; i, j : Integer; begin Write("Type a string: "); ReadLn(s); i := 1; j := length(s); repeat if not (s[i] in ["0","1"]) then begin WriteLn("Invalid input at " + IntToStr(i)); exit; end; if (s[i] = "1") then begin while (j > i) do begin if (s[j] = "0") then begin s[j] := "1"; s[i] := "0"; break; end; Dec(j); end; end; Inc(i); until (i >= length(s)); WriteLn("Sorted list: ", s); end.

Вот, переписал на FPC :)

← →
jack128 © (2006-12-22 15:39) [19]

jack128 © (22.12.06 15:38) [17]
а. Туплю.

← →
Ega23 © (2006-12-22 15:40) [20]

> как это можно по 2 отбрасывать? Ведь в одном забеге могут
> участвовать самые быстрые тараканы, а двух других - самые
> медленные из этих 9ти..
>

Пускаем 5, отбрасываем двух, добавляем двух, отбрасываем двух, добавляем двух.
3 забега. Итого с предыдущими 6 - 9.

← →
palva © (2006-12-22 15:42) [21]

1 - достаточно 2
Если представить диск циферблатом, то один устанавливаем над цифрой 3, друой над цифрой 6. Как только первый выдаст 1 следим за вторым датчиком. Если он выдаст 1, то по часовой стрелке, если 0, то против часовой.

← →
Alexis © (2006-12-22 15:51) [22]

2 MBo

> 9. Числа Стирлинга 2 рода определяются так:
> S(n,1) = 1
> S(n,n) = 1
> S(n,k) = S(n-1, k-1) + k*S(n-1,k)
> По определению нетрудно составить рекурсивную функцию, но
> она будет довольно
> медленной для значений параметров, скажем, до миллиона.
> Как более эффективно вычислить S(n,k)?

Динамическое программирование использовать? Или правильным решением является другой метод?
Дополнительную память можно использовать неограниченно (напримердинамический массив)или решение этого не допускает?

← →
MBo © (2006-12-22 15:57) [23]

>Дополнительную память можно использовать неограниченно (напримердинамический массив)или решение этого не допускает?

Можно, но не слишком расточительно

← →
Кабан © (2006-12-22 15:58) [24]

1) устраиваем забег 5-ок
2) в каждой 5-ке отбрасываем по два таракана
2) устраиваем забег лидеров
3) отбрасываем две 3-ки
4) остаются следующие тараканы (номер тройки, место)
11 12 13
21 22 23
31 32 33
5) 11 - автоматически проходит в финал
6) 23, 32, 33 в финал попасть уже не могут,
7) устраиваем забег из тараканов 12, 13, 21, 22 и 31, в финал проходят два таракана

итого 7 забегов

← →
GRAND25 © (2006-12-22 16:02) [25]

> Извиняюсь, что на си.

Очень хорошо, что извинился. Молодец! Все бы так...

← →
MBo © (2006-12-22 16:03) [26]

>palva © (22.12.06 15:30) [15]
Логика правильная, но не всё учтено, можно еще оптимизировать

>palva © (22.12.06 15:42) [21]
>1 - достаточно 2

Это верно, а вот обеспечивает ли помещение датчиков под углом 90 градусов лучшее ожидаемое время?

>Кабан © (22.12.06 15:18) [13]
>7) 1/4

Моделирование показывает заметно меньшую величину.

← →
novill © (2006-12-22 16:03) [27]

тараканов можно определить в 4 забега

← →
palva © (2006-12-22 16:06) [28]

2 - Когда у нас осталось 9 претендентов, то победивший в забеге лидеров является самым быстрым, поэтому мы его можем уже считать отобранным. Из оставшихся восьми возьмем 5 для очередного забега. Трое пришедших последними определенно не принадлежат тройке лидеров, поскольку двое оередили их в данном забеге, а еще один уже признан самым быстрым. Поэтому трех последних можно отбросить. Среди оставшихся пяти провести еще один забег и снова отбросить трех. Всего получается 8 забегов.

2 MBo

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

А счет начинается с человека, стоящего сразу следующим после выбывшего или с некого условного начала круга? Т.е. если M=2, то 1-2-3-4-5-...
2-ой выбыл 1-3-4-5-... 4-ый выбыл 1-3-5-...
или
2-ой выбыл 1-3-4-5-... 3-ий выбыл 1-4-5-...

> [30] MBo © (22.12.06 16:06)

> 4) остаются следующие тараканы (номер тройки, место)
> 11 12 13
> 21 22 23
> 31 32 33
> 5) 11 - автоматически проходит в финал
> 6) 23, 32, 33 в финал попасть уже не могут

Почему?

Пусть 5 человек, нумеруем, например, от 0 до 4, выбывает каждый второй.
Тогда последовательность отстрела
1 3 0 4, остается 2
Если удобнее нумерация с единицы, то 2 4 1 5, остается 3

novill © (22.12.06 16:11) [35]
> почему 32 не может быть быстрее 22?
Может, но он медленне чем 31 21 11, и потому не попадает в призеры.

Пятничные задачки ;) Найти похожие ветки