Задачка для собеседования

[Peter Almazov]

На форуме по Дракону привели пример "из области автоматного программирования" http://forum.oberoncore.ru/viewtopic.php?p=75830#p75830

К мусору в головах любителей Дракона давно бы уже надо привыкнуть, но он не перестает меня поражать. Ну да, ладно, хрен с ними.

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

Чтобы не портить удовольствие желающим решить, выкладываю свое решение запароленным.

[ilovb]

Продублирую тут:

Задача ставится следующим образом. Даны два массива. Каждый из них
содержит последовательность неповторяющихся чисел, завершающуюся нулем.
Второй массив содержит ту же, что и в первом, последовательность, но
включает вставки из чисел, отсутствующих в первом массиве. Например:

М1 = 2 4 5 7 8 9 12 13 0
М2 = 2 4 5 21 23 24 7 8 9 12 13 0
           --------
(подчеркнута вставка).

Программа должна сравнить два массива и напечатать вставки, встречающиеся
во втором массиве.

[ilovb]

Мой вариант под паролем 

[Geniepro]

Код: [Выделить]

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 z

Код: [Выделить]

Main> :main
[21,23,24]
[31,32,33]

[DIzer]

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

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

Код: [Выделить]

....
  while a[i] <> 0 do begin
  while a[i] <> b[j] do begin
     write (b[j], '  ');
     inc(j)
     end;
  writeln;   
  inc(i)
  end
....


[DIzer]

Код: [Выделить]

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 z

Код: [Выделить]

Main> :main
[21,23,24]
[31,32,33]

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

[DIzer]

посмотрел оригинальное сообщение (Дмитрий_ВБ) - что могу сказать... драконофилия - это заразная болезнь... как и оберономания.

[Geniepro]

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

Эээ, речь же шла об автоматном подходе, вот я и сделал автомат )))

[Valery Solovey]

Код: [Выделить]

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.

[ilovb]

решается "в лоб" за 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

[ilovb]

А вообще пожалуй соглашусь с 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

[Geniepro]

Инварианты-то де, инварианты???

[DIzer]

Нет inc(j) в основном цикле. И a[ i ] <> 0 нужно заменить на b[ i ] <> 0

    не угадали но ошибка, разумеется, есть - не дописан возможный "хвост" в массиве b  (не рассмотрен случай когда "вставка" находится в конце  массива b)

[ilovb]

Там кстати есть тест покрывающий большинство случаев:

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

[DIzer]

Инварианты-то де, инварианты???

чего , инварианты--?