Oberon space
General Category => Общий раздел => Тема начата: Peter Almazov от Ноябрь 04, 2012, 08:26:17 pm
-
На форуме по Дракону привели пример "из области автоматного программирования" http://forum.oberoncore.ru/viewtopic.php?p=75830#p75830
К мусору в головах любителей Дракона давно бы уже надо привыкнуть, но он не перестает меня поражать. Ну да, ладно, хрен с ними.
А задачка-то хорошая. Вполне годится для собеседования.
Для простоты можно не требовать выводить непрерывные куски вставок отдельно, а выводить все подряд. При решении можно вспомнить и синтаксические диаграммы, и цикл Дейкстры.
Чтобы не портить удовольствие желающим решить, выкладываю свое решение запароленным.
-
Продублирую тут:
Задача ставится следующим образом. Даны два массива. Каждый из них
содержит последовательность неповторяющихся чисел, завершающуюся нулем.
Второй массив содержит ту же, что и в первом, последовательность, но
включает вставки из чисел, отсутствующих в первом массиве. Например:
М1 = 2 4 5 7 8 9 12 13 0
М2 = 2 4 5 21 23 24 7 8 9 12 13 0
--------
(подчеркнута вставка).
Программа должна сравнить два массива и напечатать вставки, встречающиеся
во втором массиве.
-
Мой вариант под паролем :)
-
m1 = [2, 4, 5, 7, 8, 9, 12, 13, 20, 0] :: [Int]
m2 = [2, 4, 5, 21, 23, 24, 7, 8, 9, 12, 13, 31, 32, 33, 20, 0] :: [Int]
main = do
let mss = comps m1 m2
mapM_ print mss
comps :: (Eq a) => [a] -> [a] -> [[a]]
comps xs' ys' = reverse $ comps' xs' ys' [] True
where
comps' [] __ zs _ = zs
comps' __ [] zs _ = zs
comps' (x:xs) (y:ys) zs True | x == y = comps' xs ys zs True
comps' (x:xs) (y:ys) zs True | x /= y = comps' (x:xs) ys ( [y] :zs) False
comps' (x:xs) (y:ys) (z:zs) False | x /= y = comps' (x:xs) ys ((y:z):zs) False
comps' (x:xs) (y:ys) (z:zs) False | x == y = comps' xs ys ( z' :zs) True
where z' = reverse zMain> :main
[21,23,24]
[31,32,33]
-
А задачка-то хорошая. Вполне годится для собеседования.
Для простоты можно не требовать выводить непрерывные куски вставок отдельно, а выводить все подряд. При решении можно вспомнить и синтаксические диаграммы, и цикл Дейкстры.
куда на собеседование - в детский сад? - если я правильно понял то это классическая однопроходная задача , решается "в лоб" за 3 минуты..
....
while a[i] <> 0 do begin
while a[i] <> b[j] do begin
write (b[j], ' ');
inc(j)
end;
writeln;
inc(i)
end
....
-
m1 = [2, 4, 5, 7, 8, 9, 12, 13, 20, 0] :: [Int]
m2 = [2, 4, 5, 21, 23, 24, 7, 8, 9, 12, 13, 31, 32, 33, 20, 0] :: [Int]
main = do
let mss = comps m1 m2
mapM_ print mss
comps :: (Eq a) => [a] -> [a] -> [[a]]
comps xs' ys' = reverse $ comps' xs' ys' [] True
where
comps' [] __ zs _ = zs
comps' __ [] zs _ = zs
comps' (x:xs) (y:ys) zs True | x == y = comps' xs ys zs True
comps' (x:xs) (y:ys) zs True | x /= y = comps' (x:xs) ys ( [y] :zs) False
comps' (x:xs) (y:ys) (z:zs) False | x /= y = comps' (x:xs) ys ((y:z):zs) False
comps' (x:xs) (y:ys) (z:zs) False | x == y = comps' xs ys ( z' :zs) True
where z' = reverse zMain> :main
[21,23,24]
[31,32,33]
вот именно за это я и нелюблю хаскилеров :o - какашку могут сделать из чего угодно... пользуясь вовсю тем, что нормальным людям лень всматриваться в эту х..ню
-
посмотрел оригинальное сообщение (Дмитрий_ВБ) - что могу сказать... драконофилия - это заразная болезнь... как и оберономания.
-
вот именно за это я и нелюблю хаскилеров :o - какашку могут сделать из чего угодно... пользуясь вовсю тем, что нормальным людям лень всматриваться в эту х..ню
Эээ, речь же шла об автоматном подходе, вот я и сделал автомат )))
-
PROCEDURE ddd (IN base, mod : ARRAY OF INTEGER);
VAR i, j : INTEGER;
BEGIN
(* Считаем, что массивы правильные. То есть, mod - это base со вставками, а не просто очень похожий массив. *)
i := 0; j := 0;
WHILE base[i] # 0 DO
WHILE (base[j] # 0) OR (base[i] # mod[j]) DO
Log.WriteInt(mod[j]);
j := j + 1;
END;
Log.WriteLn();
WHILE (base[i] # 0) OR (base[i] = mod[j]) DO
i := i + 1;
j := j + 1;
END
END
END ddd.
-
решается "в лоб" за 3 минуты..
....
while a[i] <> 0 do begin
while a[i] <> b[j] do begin
write (b[j], ' ');
inc(j)
end;
writeln;
inc(i)
end
....
Нет inc(j) в основном цикле. И a[ i ] <> 0 нужно заменить на b[ i ] <> 0
-
А вообще пожалуй соглашусь с DIzer. Задача слишком простая.
мой вариант:
Процедура СравнитьМассивы(Массив1, Массив2)
Разница = 0;
Для Индекс1 = 0 По Массив1.Количество() - 1 Цикл
Индекс2 = Индекс1 + Разница;
Пока Массив1[Индекс1] <> Массив2[Индекс2] Цикл
Сообщить(Массив2[Индекс2]);
Индекс2 = Индекс2 + 1;
КонецЦикла;
Разница = Индекс2 - Индекс1;
КонецЦикла;
КонецПроцедуры
http://oberspace.dyndns.org/index.php/topic,365.msg9821.html#msg9821
пароль: oberspace.dyndns.org
-
Инварианты-то де, инварианты???
-
Нет inc(j) в основном цикле. И a[ i ] <> 0 нужно заменить на b[ i ] <> 0
;) не угадали но ошибка, разумеется, есть - не дописан возможный "хвост" в массиве b (не рассмотрен случай когда "вставка" находится в конце массива b)
-
Там кстати есть тест покрывающий большинство случаев:
static int M1[] = { 1, 2, 3, 4, 5, 6, 7, 0 };
static int M2[] = { 28, 1, 2, 3, 4, 5, 6, 7, 0 };
static int M3[] = { 38, 39, 30, 1, 2, 3, 4, 5, 6, 7, 0 };
static int M4[] = { 1, 2, 3, 4, 5, 6, 7, 48, 0 };
static int M5[] = { 1, 2, 3, 4, 5, 6, 7, 58, 59, 50, 0 };
static int M6[] = { 1, 2, 3, 68, 4, 5, 6, 7, 0 };
static int M7[] = { 1, 2, 3, 78, 79, 70, 4, 5, 6, 7, 0 };
static int M8[] = { 1, 2, 80, 81, 82, 3, 4, 5, 83, 84, 6, 7, 85, 86, 87,0 };
...
collation M1 & M2
insert: 28
collation M1 & M3
insert: 38 39 30
collation M1 & M4
insert: 48
collation M1 & M5
insert: 58 59 50
collation M1 & M6
insert: 68
collation M1 & M7
insert: 78 79 70
collation M1 & M8
insert: 80 81 82
insert: 83 84
insert: 85 86 87
-
Инварианты-то де, инварианты???
чего , инварианты--?
-
Вариант для случая, когда длина массивов неизвестна:
Процедура СравнитьМассивы2(Массив1, Массив2)
Разница = 0;
Индекс1 = 0;
Индекс2 = 0;
Пока Массив2[Индекс2] <> 0 Цикл
Индекс2 = Индекс1 + Разница;
Пока Массив1[Индекс1] <> Массив2[Индекс2] Цикл
Сообщить(Массив2[Индекс2]);
Индекс2 = Индекс2 + 1;
КонецЦикла;
Разница = Индекс2 - Индекс1;
Индекс1 = Индекс1 + 1;
КонецЦикла;
КонецПроцедуры
-
ilovb - та же байда.. хвоста нет... в терминах инвариантов задачи не выполняется not ( (a=0) and (b[j]=0) )
-
Я прогнал на тестах. Все правильно вроде.
Log:
28
----------------
38
39
30
----------------
48
----------------
58
59
50
----------------
68
----------------
78
79
70
----------------
80
81
82
83
84
85
86
87
----------------
-
Странный глюк не могу выправить , должно быть not ( (a =0) and (b[j] = 0) )
-
блин... a - не печатается...
-
a[i] не печатается..
-
a[i] не печатается..
Нужно пробелы ставить [ i ] ;)
зы Это тэг италика срабатывает. Меня тоже уже задолбало :)
-
...должно быть not ( (a[ i ] =0) and (b[ j ] = 0) )
Не понял. Зачем?
-
формальная констатация факта , что мы не просмотрели все элементы в массивах... -- но обратите внимание - я его в тот момент, когда писал кусок НЕ ЗНАЛ (ибо я не въехал в задачу).
-
Тык у меня же Массив2[Индекс2] <> 0
этого достаточно т.к.:
Длина(Массив2) >= Длина(Массив1)
-
я говорил про свой алгоритм... у вас он ДРУГОЙ (точнее , я решал задачу "в лоб", вы заменяли координаты -соответственно и ВИД этого инварианта в ВАШЕЙ системе координат другой)
-
Циклом дейкстры наверно так будет:
procedure compare(a, b)
i = 0;
j = 0;
while true do
if a[i] <> b[j] then
message(b[j]);
inc(j);
elsif a[i] <> 0 then
inc(i);
inc(j);
else
break;
endif;
enddo
endprocedure
ps Самый простой код однако ???
-
Это практически вариант Valery Solovey. Только в более каноническом виде :)
ps do loop в 1С нету, потому while true
-
мне не нравится - напрягает (вариант Валерия также), правда это все цветочки , по сравнению с тем, что сделал Geniepro
-
А на ruby эта задача решается так:
b - a
;D ;D ;D
-
Собсна вот:
Вычитание массивов — возвращает новый массив, который копирует оригинальный массив, но удаляет из него элементы, которые есть в другом массиве. (http://ru.wikibooks.org/wiki/Ruby/%D0%A1%D0%BF%D1%80%D0%B0%D0%B2%D0%BE%D1%87%D0%BD%D0%B8%D0%BA/Array#Array.23-)
-
А вот на python'е
>>> lst1 = [1, 5, 1, 3, 4, 2, 6]
>>> lst2 = [1, 2]
>>> list(set(lst1).difference(lst2))
[3, 4, 5, 6]
-
А на ruby эта задача решается так:
b - a
;D ;D ;D
ну и что... даже в Паскале - сделайте пару соответствующих множеств.. и выведите их разность...
-
другое дело, что таким образом НЕ решается задача о ВСТАВКАХ (в том виде , каком она сформулирована в оригинале)
-
А задачка-то хорошая. Вполне годится для собеседования.
Для простоты можно не требовать выводить непрерывные куски вставок отдельно, а выводить все подряд. При решении можно вспомнить и синтаксические диаграммы, и цикл Дейкстры.
куда на собеседование - в детский сад? - если я правильно понял то это классическая однопроходная задача , решается "в лоб" за 3 минуты..
Для собеседования задачка отличная. Достаточно простая чтобы человек в состоянии стресса смог за 5 минут её решить.
И нет, задачка не слишком простая. У меня на собеседованиях частенько народ функцию strlen написать не может (определяет длину null terminated строки), а уж strdup - это вообще высший пилотаж. А в качестве фаталисти частенько используется задача - распечатать односвязный список с хвоста.
Что забавно - частенько народ имеющий опыт работы порядка 4-5 лет решает подобное хуже чем вчерашние студенты (а студенты, имеющие опыт работы скажем в Интеле решаеют задачки хуже чем не имеющие оного опыта работы, зато денег хотят раза в 2-3 больше).
-
Для собеседования задачка отличная. Достаточно простая чтобы человек в состоянии стресса смог за 5 минут её решить.
да , за пять минут ее решить можно не напрягаясь... что же... будем считать ее хорошей задачей для приема на работу в которой под воздействием стресса требуется ответственно принимать простые решения за 5 минут...
-
У нас на собеседовании обычно нужно решить задачу строк в 200-400, и дается на это неделя (там еще проектирование структуры БД под задачу). Элементарная алгоритмика мало интересна.
-
У нас на собеседовании обычно нужно решить задачу строк в 200-400, и дается на это неделя (там еще проектирование структуры БД под задачу). Элементарная алгоритмика мало интересна.
у вас другая специфика... хотя .. когда я работал в этой области.. реактивность была КРАЙНЕ важна.. (заказчик более охотно платил если проблемы решались у него на глазах, правда одна проблема возникала.. содрать с него БОЛЬШУЮ сумму за раз довольно проблематично) ..
-
Хм... может заведем раздел и Абрамяна прорешаем на обероне? ;D
-
а я и так студентом даю его... на родном ему (учебнику) ПаскалеABC..
-
и потом по-Оберонистому будет Потопахин.. а у нас есть (был)? Химик на это... :D
-
Для собеседования задачка отличная. Достаточно простая чтобы человек в состоянии стресса смог за 5 минут её решить.
да , за пять минут ее решить можно не напрягаясь... что же... будем считать ее хорошей задачей для приема на работу в которой под воздействием стресса требуется ответственно принимать простые решения за 5 минут...
На самом собеседовании смысла не имеет давать что-то сложнее в плане задачек которые человек должен решить до конца (а не обозначить общее направление решения). Если человек на собеседовании понравился и мы ему тоже понравились, то дается еще задание на дом, которое уже близко к предметной области работы.
-
...заказчик более охотно платил если проблемы решались у него на глазах, правда одна проблема возникала...
Ну так и есть у нас... Но у приходящих кандидатов (вчерашних студентов) опыта нет, и накатать более 50 строк just in time мало кто может.
Кодеры со стажем более 2 лет могут 1-2k строк писать на глазах у заказчика, поддерживая беседу при этом :)
-
...заказчик более охотно платил если проблемы решались у него на глазах, правда одна проблема возникала...
Ну так и есть у нас... Но у приходящих кандидатов (вчерашних студентов) опыта нет, и накатать более 50 строк just in time мало кто может.
Кодеры со стажем более 2 лет могут 1-2k строк писать на глазах у заказчика, поддерживая беседу при этом :)
я про это и говорю... поскольку обычная форма отчета - час.. и ставка его фиксированная работодатель видит , сколько в принципе за него можно сделать... и начинается вонь с менеджментом "родной конторы".
-
На самом собеседовании смысла не имеет давать что-то сложнее в плане задачек которые человек должен решить до конца (а не обозначить общее направление решения). Если человек на собеседовании понравился и мы ему тоже понравились, то дается еще задание на дом, которое уже близко к предметной области работы.
зависит от работы... если работа регулярная и не "в поле" (БЕЗ СТРЕССА)- ИМХО нет смысла давать их вообще..
-
А вообще, Пабсовики - молодцы... вон какую web -ide http://pascalabc.net/WDE/ (http://pascalabc.net/WDE/)отгрохали за год... у коровят же воз и ныне там..
-
:) одна беда.. говенистость компилятора в купе.. с "прелестями" дот. нета никуда не делась.. просто перешла на другой уровень..., как у Шума.. когда он делал свой жаболог..
-
Бегло посмотрел и не увидел ни одного правильного решения.
Все сломаются, если первый массив состоит из одного нуля. Тогда все содержимое второго - это вставка.
P.S. Решение Geniepro ниасилил..
-
Бегло посмотрел и не увидел ни одного правильного решения.
Все сломаются, если первый массив состоит из одного нуля. Тогда все содержимое второго - это вставка.
да , так оно и есть... это тот хвост - который "зевнул" я
while b[j]<>0 do begin
write ( b[j],' ');
inc(j)
end;
-
Бегло посмотрел и не увидел ни одного правильного решения.
Все сломаются, если первый массив состоит из одного нуля. Тогда все содержимое второго - это вставка.
Все мои 3 варианта работают правильно...
-
Что забавно - частенько народ имеющий опыт работы порядка 4-5 лет решает подобное хуже чем вчерашние студенты (а студенты, имеющие опыт работы скажем в Интеле решаеют задачки хуже чем не имеющие оного опыта работы, зато денег хотят раза в 2-3 больше).
Гы гы.... особенности Нижнигородской конюшни ( Интел - стойбище ставит свое клеймо, однако) ;D
-
мне не нравится - напрягает (вариант Валерия также), правда это все цветочки , по сравнению с тем, что сделал Geniepro
Ой да ладно, Вы хоть видели вариант из исходного сообщения, тот, который на сях? )))
-
мне не нравится - напрягает (вариант Валерия также), правда это все цветочки , по сравнению с тем, что сделал Geniepro
Ой да ладно, Вы хоть видели вариант из исходного сообщения, тот, который на сях? )))
Видел... , но вы же не относите себя к дракофилам? :D.
я же сказал... что это больные люди.. и толмуд ихний так и называется.. "Психология программирования КА".. у Оберономанов есть своя библия...
-
Бегло посмотрел и не увидел ни одного правильного решения.
Все сломаются, если первый массив состоит из одного нуля. Тогда все содержимое второго - это вставка.
P.S. Решение Geniepro ниасилил..
Ничего не знаю, у меня всё чотко!
m1 = [0]
m2 = [2, 4, 5, 21, 23, 24, 7, 8, 9, 12, 13, 31, 32, 33, 20, 0]
....Main> :main
[2,4,5,21,23,24,7,8,9,12,13,31,32,33,20]
PS. И не всё содержимое второго, а только то, что до последнего элемента, равного нулю...
-
Ничего не знаю, у меня всё чотко!
А ваше решение никто внимательно не смотрел.. - лично я, как увидел - злобно сплюнув, матернулся... - о чем и отписал..
-
P.S. Решение Geniepro ниасилил..
У меня же там натуральный конечный автомат, оформленный в виде хаскельной вариации на тему "цикла Дейкстры", гоняющий туда-сюда состояния переходов и всё такое )))
Что там непонятного -- непонятно ))
-
У меня же там натуральный конечный автомат, оформленный в виде хаскельной вариации на тему "цикла Дейкстры", гоняющий туда-сюда состояния переходов и всё такое )))
Что там непонятного -- непонятно ))
Вот вот, в этом вся сущность Хаскилеров... фармазоны недобитые... ;D
-
У меня же там натуральный конечный автомат, оформленный в виде хаскельной вариации на тему "цикла Дейкстры", гоняющий туда-сюда состояния переходов и всё такое )))
Что там непонятного -- непонятно ))
Вот вот, в этом вся сущность Хаскилеров... фармазоны недобитые... ;D
Зато программам на хаскелле не нужна обфускация, вот!
-
Бегло посмотрел и не увидел ни одного правильного решения.
Все сломаются, если первый массив состоит из одного нуля. Тогда все содержимое второго - это вставка.
Все мои 3 варианта работают правильно...
Да, я тут не прав. Когда я решал, то трактовал последний 0 как конец последовательности, особый случай. И не учел, что он может участвовать в сравнении с внутренностями массива и никогда не совпадет с ними. Просмотрел возможность схалтурить.
Если бы учел, то изменил условия – выкинул бы 0 и, возможно, заменил бы массивы на списки.
Пароль: gga1mb
Вот текст для удобства:
class Program {
static int[] M1 = { 1, 2, 3, 4, 5, 6, 7, 0 };
static int[] M2 = { 28, 1, 2, 3, 4, 5, 6, 7, 0 };
static int[] M3 = { 38, 39, 30, 1, 2, 3, 4, 5, 6, 7, 0 };
static int[] M4 = { 1, 2, 3, 4, 5, 6, 7, 48, 0 };
static int[] M5 = { 1, 2, 3, 4, 5, 6, 7, 58, 59, 50, 0 };
static int[] M6 = { 1, 2, 3, 68, 4, 5, 6, 7, 0 };
static int[] M7 = { 1, 2, 3, 78, 79, 70, 4, 5, 6, 7, 0 };
static int[] M8 = { 1, 2, 80, 81, 82, 3, 4, 5, 83, 84, 6, 7, 85, 86, 87, 0 };
static void collation(int[] a, int[] b) {
int i = 0, j = 0;
//bool newIns = true;
while (b[j] != 0) {
if (a[ i] == 0 || a[ i] != b[j]) {
//if (newIns) {
// newIns = false;
// System.Console.WriteLine();
// System.Console.WriteLine("insert: ");
//}
System.Console.Write(b[j] + " ");
j++;
} else {
i++; j++;
//newIns = true;
}
}
}
static void Main(string[] args) {
System.Console.WriteLine("\n\n collation M1 & M2");
collation(M1, M2);
System.Console.WriteLine("\n\n collation M1 & M3");
collation(M1, M3);
System.Console.WriteLine("\n\n collation M1 & M4");
collation(M1, M4);
System.Console.WriteLine("\n\n collation M1 & M5");
collation(M1, M5);
System.Console.WriteLine("\n\n collation M1 & M6");
collation(M1, M6);
System.Console.WriteLine("\n\n collation M1 & M7");
collation(M1, M7);
System.Console.WriteLine("\n\n collation M1 & M8");
collation(M1, M8);
System.Console.ReadLine();
}
} Для наглядности можно выкинуть комментарии (кусок решения с раздельным выводом вставок):
static void collation(int[] a, int[] b) {
int i = 0, j = 0;
while (b[j] != 0) {
if (a[ i] == 0 || a[ i] != b[j]) {
System.Console.Write(b[j] + " ");
j++;
} else {
i++; j++;
}
}
}
-
что же мой вариант...
program ttt;
{$APPTYPE CONSOLE}
const
M1:array [0..7] of integer = ( 1, 2, 3, 4, 5, 6, 7, 0 );
M2:array [0..8] of integer = ( 28, 1, 2, 3, 4, 5, 6, 7, 0 );
M3:array [0..10] of integer = ( 38, 39, 30, 1, 2, 3, 4, 5, 6, 7, 0 );
M4:array [0..8] of integer = ( 1, 2, 3, 4, 5, 6, 7, 48, 0 );
M5:array [0..10] of integer = ( 1, 2, 3, 4, 5, 6, 7, 58, 59, 50, 0 );
M6:array [0..8] of integer = ( 1, 2, 3, 68, 4, 5, 6, 7, 0 );
M7:array [0..10] of integer = ( 1, 2, 3, 78, 79, 70, 4, 5, 6, 7, 0 );
M8:array [0..15] of integer = ( 1, 2, 80, 81, 82, 3, 4, 5, 83, 84, 6, 7, 85, 86, 87,0 );
procedure PrintDiff(a,b:array of integer);
var i,j:Integer;
begin
i:=0; j:=0;
while a[i] <> 0 do begin //общая внутренность
while a[i] <> b[j] do begin
write (b[j], ' ');
inc(j);
end;
writeln;
inc(i);
inc(j);
end;
while b[j] <> 0 do begin // пропущенный мною хвост
write (b[j], ' ');
inc(j);
end;
end;
begin
PrintDiff(M1,M8);
Readln;
end.
-
function PrintDiff(a,b)
local i, j = 1, 1
while b[j] ~= 0 do
if b[j] == a[i] then i = i+1 else print(b[j]) end
j = j+1
end
end
;)
-
Тут уже нет ничего нового.
Интересно было бы увидеть формулировку инварианта цикла.
У меня она есть, но я ей не вполне доволен. Может кто-нибудь предложит поинтереснее.
Паролить свою уж не буду :)
-
Да, trurl, ваш вариант пожалуй самый красивый :)
-
Да, trurl, ваш вариант пожалуй самый красивый :)
ilovb - а вы уверены, что за 5 минут отведенных на эту задачу на собеседовании - у вас будет время "красоваться"....? вот я вы..лся потратив на решение "в лоб" 1.5 минуты не стал его проверять - и результат на лицо... :D
-
Ну если кандидат решит эту задачу также как trurl, то это уже о чем то говорит. :)
-
Ну если кандидат решит эту задачу также как trurl, то это уже о чем то говорит.
если за 5 минут - то да... а если нет.. ?
-
5 минут на самом деле довольно экстремальные условия для собеседования. Опытные кодеры быстро пишут хороший код не потому что у них IQ=200, а потому что они пишут по памяти...
А на собеседовании имхо "хороший код" - это тараканы работодателя (ну или специфика работы) ;)
-
у вас будет время "красоваться"....?
Ну, "красоваться" здесь только
while b[j] ~= 0 doвместо первоначального "пятиминутного"
while a[i] ~= 0 and b[j] ~= 0 doИ я тоже не стал проверять. :)
-
ну мы же обсуждали с Алексеем для чего и в каких случаях на собеседованиях возможны такие задачи... с другой стороны... эту задачу подсунул Петр... я указал на то, что если речь идет о высокой квалификации то поиск ее решения должен быть ограничена по времени.. вот где- то так...
-
у вас будет время "красоваться"....?
Ну, "красоваться" здесь только
while b[j] ~= 0 doвместо первоначального "пятиминутного"
while a[i] ~= 0 and b[j] ~= 0 doИ я тоже не стал проверять. :)
да ИМХО на практике при решении подобных задач в "экстремальных" условиях у вас ровно два подхода (если конечно такая задача не встречалась на практике)
1. Сводить решение к модификации "стандартных" задач
2. Найти его "в лоб" построив алгоритм исходя из понимания задачи.
Собственно почему. я настаивал на ограничении времени на задачу - прикинул.. и оказалось, что построить решение "в лоб" можно за несколько минут...
-
Для кодеров кстати, помимо умения решать задачи, очень важна обучаемость.
Существуют человеки которые кроме лаб в универе ничего в жизни не кодили. Но при этом отлично обучаются. Объяснил ему один раз и все. Чувак инфу воспринял, задал пару вопросов, и пошел кодить. А есть такие, ну прям вундеркинды... и на js они покодить успели и на php, и с sql дело имели и в cpp чегой то ковырялись... Но на деле пишут страшный говнокод и переучить их невозможно.
ps Я бы даже обучаемость на первое место поставил :D
-
Для кодеров кстати, помимо умения решать задачи, очень важна обучаемость.
Существуют человеки которые кроме лаб в универе ничего в жизни не кодили. Но при этом отлично обучаются. Объяснил ему один раз и все. Чувак инфу воспринял, задал пару вопросов, и пошел кодить. А есть такие, ну прям вундеркинды... и на js они покодить успели и на php, и с sql дело имели и в cpp чегой то ковырялись... Но на деле пишут страшный говнокод и переучить их невозможно.
да и таких больше из университетов (меньше из спец. тех. вузов) - особенности обучения... НО данную способность подобными задачами не проверишь - более того, в целом я уверен, что подобные задачи гораздо лучше должны идти у представителей тех. вузов и специализированных колледжей..
-
ps Я бы даже обучаемость на первое место поставил :D
зависит от задач.. есть куча высокооплачиваемых задач , где профессиональный кодер (владеющий ЯП, стандартными либами и шаблонами проектирования) порвет "обучаемого" хмыря как "тузик грелку"...
-
Интересно было бы увидеть формулировку инварианта цикла.
Вот моё. Все общие области слева пропущены и все добавленные области слева обработаны (распечатаны).
"Области слева" = области слева от курсора.
-
Совпадает с моим.
-
Совпадает с моим.
Хотя нет, поспешил. Строго говоря, мой вариант был такой: "все отличия распечатаны".
Речь идет об интервалах [0,i) и [0,j)
-
Так и нормальный инвариант же. Почему он не устраивает?
-
Вот не нравится чем-то.
Непонятно, по какому закону расширять интервалы.
-
Если обозначить j(i) как j при котором b[ j ]=a[ i ], то
для i=0 j<=j(0)
для i>0 j(i-1)<j<=j(i)
Собственно это же сойдёт и за инвариант.
Можно играть и с таким инвариантом a[ i ]=b[ j ] , даже тот цикл от Trurl, если интерпретировать его как "два в одном", рассматривая итерацию по i как "главную" :)
Вообщем как-то так, особо не гоняясь за строгостью (лень) :)
PS. борьба с курсивом
-
Так и нормальный инвариант же. Почему он не устраивает?
А какая от него польза?
-
Вот не нравится чем-то.
Непонятно, по какому закону расширять интервалы.
То есть, непонятно, как двигаться вперёд? У нас есть два непересекающихся множества элементов. Элементы одного множества - это поддиапазоны чисел, одинаковых в обоих массивах, а элементы другого множества - это поддиапазоны чисел из второго массива, не встречающиеся в первом. Поддиапазоны непрерывны и максимальны.
Можно считать, что у нас последовательность (или массив) чередующихся элементов из обоих множеств. И инвариант говорит нам, что все элементы слева от курсора обработаны. Только обработка зависит от типа элемента, тогда как в обычном массиве обработка однородна.
Обработка элемента из первого множества заключается в его пропуске (и это делается в первой части цикла), а обработка элемента второго множества - вывод его на печать.
-
А какая от него польза?
Не очень понимаю. Польза от инвариантов? Применительно к чему?
-
Так и нормальный инвариант же. Почему он не устраивает?
А какая от него польза?
Как говорил Info21: "Всегда вспоминаю Зинаиду Гиппиус."
-
А какая от него польза?
Не очень понимаю. Польза от инвариантов? Применительно к чему?
Инвариант цикла должен помогать правильному построению цикла, иначе, следуя принципу бритвы Оккама, этот инвариант нинужен!
-
А какая от него польза?
Не очень понимаю. Польза от инвариантов? Применительно к чему?
Инвариант цикла должен помогать правильному построению цикла, иначе, следуя принципу бритвы Оккама, этот инвариант нинужен!
Geniepro, проблема не в этом... а в том, что в силу недонозначности инварианта помноженной неоднозначность алгоритма, которая, в свою очередь помножается на различия в восприятии и некоторую субьективность понятия "нужен" (в данном контексте) - то что полезно для Петра может быть бесполезно для Вас (и наоборот).
-
Например , ;D Петр утверждает что априори полезен... и поэтому на каждый чих .. ПЫТАЕТСЯ его отыскать - как результат он больше времени анализирует задачу (как следствие лучше ее понимает) и его навыки в этом анализе совершенствуются (с определенной степенью эффективности).. и как следствие - частота сделанных им ошибок меньше.. То есть что мы имеем.. - несомненную пользу.. даже в том случае если метода полное г. (эффект плацебо).
-
А вот, Geniepro, пример случая когда эта метода БЕЗУСЛОВНО ПО ФАКТУ ВРЕДНА - у меня таких 50% на группу - когда текущая степень понимания человеком решаемой задачи не позволяет ему выделить последовательность действий (алгоритм). В этом случае - эта метода просто отвлекает его от того , что РЕАЛЬНО нужно делать. Как следствие - задача вовремя не решается , а самое паскудное то, что в него входит ощущение неуверенности в своих силах...
-
Вот не нравится чем-то.
Непонятно, по какому закону расширять интервалы.
Не нравится тем, что никак не отражает существенную несимметричность ролей массивов (а задача подло провоцирует на симметричность).
Более правильный вариант выглядит так. Обозначим массивы как a и b, индексы - i и j.
Массив b в некотором роде главный. Массив a – играет роль генератора эталонных символов. Полный инвариант выглядит так: "для обработанной области массива b напечатаны все отличия, и из генератора "выбраны" все символы, встретившиеся (в нужном порядке) в b".
Отсюда логично следует тело цикла.
Берем очередной необработанный символ из массива b. Если он не совпадает с текущим символом генератора, то печатаем его. Иначе "забираем" символ из генератора (продвигаем вперед i). Конец если. Расширяем обработанную область (продвигаем вперед j).
Я трактовал последний 0 в массиве "a" как конец работы генератора. Другие авторы, не нарушая условий задачи, трактовали его как обычный символ, который никогда не встретится внутри массива b.
-
Как говорил Info21: "Всегда вспоминаю Зинаиду Гиппиус."
Новые посетители могут не понять междусобойчика. "Если надо объяснять, то не надо объяснять".
З. Гиппиус.
-
По поводу инварианта a[ i ]=b[ j ] в двух словах.
Имеем в основе два прохода по всем элементам массивов a[] и b[]
i:=0 ; while a[ i ] # 0 do i:=i+1 end
и
j:=0 ; while b[ j ] # 0 do j:=j+1 end
Все варианты решений - это организация тем или иным макаром "переключений" с одного цикла на другой и обратно.
На каждый шаг по массиву a[] организуем не менее 1 шага по массиву b[] для восстановления инварианта (совпадение значений)
а вот в "процессе" восстановления инварианта как раз и происходит "полезная работа" в этой задаче