Вверх ↑
Этот топик читают: Гость
Ответов: 5446
Рейтинг: 323
#1: 2008-02-09 11:50:14 ЛС | профиль | цитата
Для тех, кто не успел, не смог или не захотел принять участие в секции "Алгоритмы" вчера (то есть - на конкурсной основе), выкладываю здесь задачи этой секции.
Обсуждение задач и решений приветствуется.



Задача 1. РИМСКИЕ ЦИФРЫ
Создайте схему, переводящую числа, записанные римскими цифрами, в числа, записанные арабскими цифрами.

СПРАВКА: (взято из [url=http://ru.wikipedia.org/wiki/Римские цифры]Wikipedia[/url])
Римские цифры: Цифры, использовавшиеся древними римлянами в своей непозиционной системе
счисления.

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

ЧислоРимское обозначение
1I
5V
10X
50L
100C
500D
1000M


Входные данные: файл Roman.in следующего формата:


  • Строка 1: N - число строк с числами (N <= 100)
  • Строки 2..N+1: Числа, записанные римскими цифрами

Выходные данные:
файл Roman.out, содержащий N строк. Каждая строка содержит либо число, записанное арабскими циффрами,
либо слово "NONUMBER" (входная строка содержит недопустимые символы), либо слово "BADNUMBER" (ошибка в записи числа).

Ограничения:
Время: 2.0 секунды


Задача 2. ТЕЛЕФОННЫЕ НОМЕРА
Создайте схему, находящую кратчайшую последовательность слов (т.е., с наименьшим количеством слов),
соответствующую заданному номеру телефона и списку слов. Соответствие букв и цифр описывается следующей схемой:

1 ij2 abc3 def
4 gh5 kl6 mn
7 prs8 tuv9 wxy
0 oqz


Входные данные: файл Phone.in следующего формата:


  • Строка 1: N - номер телефона
  • Строка 2: M - длинна "словаря"
  • Строки 3..M+2: словарь (одно слово на строку)

Выходные данные: файл Phone.out, содержащий либо фразу, соответствующую номеру телефона,
либо слово "NOSOLUTION", если искомую фразу подобрать невозможно.

Ограничения:
Время: 2.0 секунды


Задача 3. КОРОВЫ
У фермера Джона N (2 <= N <= 50) различных коров, пронумерованных от 1 до N, и он хочет знать,
какие две из них больше всего похожи друг на друга. Он сделал цифровые фотографии размером 5х7 каждой коровы,
и хочет, чтобы вы помогли ему сравнить их.

Фотографии показывают расположение чёрных и белых пятен коровы. Вот фотографии двух разных коров:
     Корова 1      Корова 2
..X.... ...X...
.XXX... ..XX...
.XX.... .XX....
.....X. .XX..X.
.X...X. .X...X.
("X" - чёрное пятно, "." - белое)

Чтобы сравнить коров, сравнивают каждое из пятен одной коровы с соответствующим пятном другой.
"Коэффициент схожести" увеличивается на 1 для каждой совпадающей пары пятен. Пара коров, изображённых выше,
имеют коэффициент 30, так как только 5 пятен не совпадают (помечены "#" ниже):

         ++##+++
+#+++++
+++++++
+##++++
+++++++

По заданному набору коров, найдите пару с наибольшим "коэффициентом схожеси",
и выведите их номера в порядке возрастания. Наличие только одной такой пары гарантировано.

Входные данные:
файл Cow.in следующего формата:


  • Строка 1: N - число коров
  • Строки 2..N*5+1: Цифровые фотографии коров, в которых корова i изображена в строках с i*5-3 по i*5+1.

Выходные данные:
Строка, содержащая номера коров с наибольшим "коэффициентом схожести", упорядоченные по возрастанию.
карма: 1

0
vip
#1.1контекстная реклама от партнеров
Ответов: 3514
Рейтинг: 184
#2: 2008-02-09 12:03:38 ЛС | профиль | цитата
Ну реально сложно, я на первое задание три А4 листа потратил и так и не смог додуматься )
------------ Дoбавленo:

А теперь оказалось, что я ещё и задание не так понял.. я хотел переводить из арабской в римскую
карма: 0
0
Разработчик
Ответов: 26061
Рейтинг: 2120
#3: 2008-02-09 13:28:56 ЛС | профиль | цитата
Самое интересне, что транслятор делается пятью строчками IC-кода
карма: 22

0
Ответов: 5446
Рейтинг: 323
#4: 2008-02-09 13:45:38 ЛС | профиль | цитата
Так оно и понятно, что с помощью IC всё проще делается. Задумка была в том, чтобы показать, как можно без IC обойтись.
карма: 1

0
Разработчик
Ответов: 26061
Рейтинг: 2120
#5: 2008-02-09 14:54:40 ЛС | профиль | цитата
Я не стал решать первую задачу, но две реализации конвертора Арабских в Римские нарисовал (на HiAsm'e и IC для интереса). Предлагаю воткнуть в штатный конвертор этот метод. Надо, нарисую обратный метод (а iarspider, хитер )



Add(MainForm,280613,98,84)
{
Left=20
Top=105
Width=221
Height=125
Caption="DecimalToRoman"
Position=1
}
Add(IntegerArray,5682974,294,77)
{
IntArray=['M'=1000,'CM'=900,'D'=500,'CD'=400,'C'=100,'XC'=90,'L'=50,'Xl'=40,'X'=10,'IX'=9,'V'=5,'IV'=4,'I'=1]
FileFormat=1
}
Add(Memory,237103,448,126)
{
Default=String()
}
Add(Hub,12748134,147,133)
{
OutCount=3
link(onEvent1,237103:doClear,[])
link(onEvent2,13350876:doEnum,[])
link(onEvent3,4243737:Convert,[(194,153)(194,391)])
}
Add(StrCat,3358455,448,294)
{
link(onStrCat,237103:doValue,[(492,300)(492,216)(436,216)(436,132)])
link(Str1,237103:Value,[])
link(Str2,13350876:Item,[(461,233)(209,233)])
}
Add(Memory,1401807,287,203)
{
}
Add(Repeat,13396544,287,287)
{
Type=4
link(onRepeat,16756407:doOperation,[])
link(Op1,7377394:Var2,[])
link(Op2,16082805:Var2,[])
}
Add(Math,16756407,343,287)
{
OpType=1
ResultType=0
link(onResult,16357683:doEvent1,[])
link(Op1,7377394:Var3,[(349,247)])
link(Op2,16082805:Var3,[(356,261)])
}
Add(ArrayRW,8141205,294,140)
{
link(onRead,13396544:doRepeat,[(338,146)(338,220)(255,220)(255,293)])
link(Array,5682974:Array,[])
link(Index,13350876:Index,[(307,128)(261,128)(261,184)(216,184)])
}
Add(Edit,6388985,98,203)
{
Left=20
Top=10
Width=85
Text=""
DataType=1
link(onChange,8569447:doWork2,[])
}
Add(Edit,2067103,448,343)
{
Left=110
Top=10
Width=85
Text=""
link(Str,3358455:Result,[])
}
Add(Button,1396319,98,133)
{
Left=80
Top=65
Caption="Convert"
link(onClick,12748134:doEvent1,[])
}
Add(StrList,6645552,189,63)
{
Strings=#1:M|2:CM|1:D|2:CD|1:C|2:XC|1:L|2:XL|1:X|2:IX|1:V|2:IV|1:I|
}
Add(ArrayEnum,13350876,203,140)
{
link(onItem,8141205:doRead,[])
link(onEndEnum,2067103:doText,[(369,153)(369,349)])
link(Array,6645552:Array,[])
}
Add(GetDataEx,7377394,280,238)
{
link(Data,1401807:Value,[])
}
Add(GetDataEx,16082805,287,252)
{
link(Data,8141205:Item,[])
}
Add(HubEx,8569447,259,196)
{
link(onEvent,1401807:doValue,[])
}
Add(Hub,16357683,392,287)
{
link(onEvent1,8569447:doWork3,[(436,293)(436,253)(263,253)])
link(onEvent2,3358455:doStrCat,[])
}
Add(InlineCode,4243737,231,385)
{
WorkPoints=#7:Convert|
EventPoints=#6:Result|
DataPoints=#6:Number|
Code=#15:unit HiAsmUnit;|0:|9:interface|0:|21:uses kol,Share,Debug;|0:|4:type|28: THiAsmClass = class(TDebug)|10: private|0:|9: public|24: Number :THI_event;|24: Result :THI_event;|53: procedure Convert(var _Data:TData; Index:word);|5: end;|0:|14:implementation|0:|30:procedure THiAsmClass.Convert;|115:const Romans: Array[1..13] of String = ( 'I', 'IV', 'V', 'IX', 'X', 'XL', 'L', 'XC', 'C', 'CD', 'D', 'CM', 'M' );|97: Arabics: Array[1..13] of Integer = ( 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000);|15:var i: Integer;|16: str: String;|21: Decimal: integer;|5:begin|42: Decimal := ReadInteger(_Data, Number);|14: str := '';|27: for i := 13 downto 1 do|47: while ( Decimal >= Arabics[i] ) do begin|42: Decimal := Decimal - Arabics[i];|33: str := str + Romans[i];|11: end;|29: _hi_onEvent(Result, str);|4:end;|0:|4:end.|
link(Result,1824510:doText,[])
link(Number,6388985:Text,[(237,310)(104,310)])
}
Add(Edit,1824510,448,385)
{
Left=110
Top=35
Width=85
Text=""
}

карма: 22

0
Ответов: 5446
Рейтинг: 323
#6: 2008-02-09 15:29:13 ЛС | профиль | цитата
nesco, а ты крут - я более сложный алгоритм мыслил. Да, а в чём моя хитрость-то?
карма: 1

0
Гость
Ответов: 17029
Рейтинг: 0
#7: 2008-02-09 15:31:08 правка | ЛС | профиль | цитата


Редактировалось 5 раз(а), последний 2021-06-21 05:42:08
карма: 0

0
Ответов: 5446
Рейтинг: 323
#8: 2008-02-09 15:40:57 ЛС | профиль | цитата
Вот мне интересно: это я так плохо сформулировал условие 1й задачи, или у многих с глазами проблемы?
карма: 1

0
Разработчик
Ответов: 26061
Рейтинг: 2120
#9: 2008-02-09 15:49:48 ЛС | профиль | цитата
iarspider писал(а):
Да, а в чём моя хитрость-то
В обратном конверторе (каюсь , тоже попался на невнимательном чтении, подсознательно думал, что ты народу проще задачу задал), он немного сложнее, но тоже, вполне реализуем.

Вот продолжение разборок с первой задачей (пока обратное преобразование только в IC)



Add(MainForm,280613,98,84)
{
Left=20
Top=105
Width=221
Height=152
Caption="DecimalToRoman"
Position=1
}
Add(IntegerArray,5682974,294,77)
{
IntArray=['M'=1000,'CM'=900,'D'=500,'CD'=400,'C'=100,'XC'=90,'L'=50,'Xl'=40,'X'=10,'IX'=9,'V'=5,'IV'=4,'I'=1]
FileFormat=1
}
Add(Memory,237103,448,126)
{
Default=String()
}
Add(Hub,12748134,147,133)
{
OutCount=4
link(onEvent1,237103:doClear,[])
link(onEvent2,13350876:doEnum,[])
link(onEvent3,4243737:Convert,[(195,153)(195,391)])
link(onEvent4,3594571:Convert,[(195,160)(195,447)])
}
Add(StrCat,3358455,448,294)
{
link(onStrCat,237103:doValue,[(492,300)(492,216)(436,216)(436,132)])
link(Str1,237103:Value,[])
link(Str2,13350876:Item,[(461,193)(209,193)])
}
Add(Memory,1401807,287,203)
{
}
Add(Repeat,13396544,287,287)
{
Type=4
link(onRepeat,16756407:doOperation,[])
link(Op1,7377394:Var2,[])
link(Op2,16082805:Var2,[])
}
Add(Math,16756407,343,287)
{
OpType=1
ResultType=0
link(onResult,16357683:doEvent1,[])
link(Op1,7377394:Var3,[(349,247)])
link(Op2,16082805:Var3,[(356,261)])
}
Add(ArrayRW,8141205,294,140)
{
link(onRead,13396544:doRepeat,[(338,146)(338,220)(255,220)(255,293)])
link(Array,5682974:Array,[])
link(Index,13350876:Index,[(307,128)(261,128)(261,184)(216,184)])
}
Add(Edit,6388985,210,203)
{
Left=20
Top=10
Width=85
Text=""
DataType=1
link(onChange,8569447:doWork2,[])
}
Add(Edit,2067103,448,343)
{
Left=110
Top=10
Width=85
Text=""
link(Str,3358455:Result,[])
}
Add(Button,1396319,98,133)
{
Left=80
Top=90
Caption="Convert"
link(onClick,12748134:doEvent1,[])
}
Add(StrList,6645552,189,63)
{
Strings=#1:M|2:CM|1:D|2:CD|1:C|2:XC|1:L|2:XL|1:X|2:IX|1:V|2:IV|1:I|
}
Add(ArrayEnum,13350876,203,140)
{
link(onItem,8141205:doRead,[])
link(onEndEnum,2067103:doText,[(369,153)(369,349)])
link(Array,6645552:Array,[])
}
Add(GetDataEx,7377394,280,238)
{
link(Data,1401807:Value,[])
}
Add(GetDataEx,16082805,287,252)
{
link(Data,8141205:Item,[])
}
Add(HubEx,8569447,259,196)
{
link(onEvent,1401807:doValue,[])
}
Add(Hub,16357683,392,287)
{
link(onEvent1,8569447:doWork3,[(436,293)(436,253)(263,253)])
link(onEvent2,3358455:doStrCat,[])
}
Add(InlineCode,4243737,210,385)
{
WorkPoints=#7:Convert|
EventPoints=#6:Result|
DataPoints=#6:Number|
Code=#15:unit HiAsmUnit;|0:|9:interface|0:|21:uses kol,Share,Debug;|0:|4:type|28: THiAsmClass = class(TDebug)|10: private|0:|9: public|24: Number :THI_event;|24: Result :THI_event;|53: procedure Convert(var _Data:TData; Index:word);|5: end;|0:|14:implementation|0:|30:procedure THiAsmClass.Convert;|115:const Romans: Array[1..13] of String = ( 'I', 'IV', 'V', 'IX', 'X', 'XL', 'L', 'XC', 'C', 'CD', 'D', 'CM', 'M' );|97: Arabics: Array[1..13] of Integer = ( 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000);|15:var i: Integer;|16: str: String;|21: Decimal: integer;|5:begin|42: Decimal := ReadInteger(_Data, Number);|14: str := '';|27: for i := 13 downto 1 do|47: while ( Decimal >= Arabics[i] ) do begin|42: Decimal := Decimal - Arabics[i];|33: str := str + Romans[i];|11: end;|29: _hi_onEvent(Result, str);|4:end;|0:|4:end.|
link(Result,1824510:doText,[])
link(Number,6388985:Text,[])
}
Add(Edit,1824510,448,385)
{
Left=110
Top=35
Width=85
Text=""
}
Add(InlineCode,3594571,448,441)
{
WorkPoints=#7:Convert|
EventPoints=#6:Result|
DataPoints=#6:Number|
Code=#15:unit HiAsmUnit;|0:|9:interface|0:|21:uses kol,Share,Debug;|0:|4:type|28: THiAsmClass = class(TDebug)|10: private|0:|9: public|24: Number :THI_event;|24: Result :THI_event;|53: procedure Convert(var _Data:TData; Index:word);|5: end;|0:|14:implementation|0:|30:procedure THiAsmClass.Convert;|115:const Romans: Array[1..13] of String = ( 'I', 'IV', 'V', 'IX', 'X', 'XL', 'L', 'XC', 'C', 'CD', 'D', 'CM', 'M' );|97: Arabics: Array[1..13] of Integer = ( 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000);|17:var i,p: Integer;|16: str: String;|21: Decimal: integer;|5:begin|37: str := ReadString(_Data, Number);|17: Decimal := 0;|12: i := 13;|11: p := 1;|35: while p <= Length(str) do begin|66: while Copy(str, p, Length(Romans[i])) <> Romans[i] do begin|17: Dec(i);|29: if i = 0 then exit;|11: end;|39: Decimal := Decimal + Arabics[i];|34: p := p + Length(Romans[i]);|8: end;|33: _hi_onEvent(Result, Decimal);|4:end;|0:|4:end.|
link(Result,14239851:doText,[])
link(Number,1824510:Text,[])
}
Add(Edit,14239851,518,441)
{
Left=110
Top=60
Width=85
Text=""
}

карма: 22

0
Гость
Ответов: 17029
Рейтинг: 0
#10: 2008-02-09 15:56:18 правка | ЛС | профиль | цитата


Редактировалось 5 раз(а), последний 2021-06-21 05:42:08
карма: 0

0
Ответов: 5446
Рейтинг: 323
#11: 2008-02-09 15:59:49 ЛС | профиль | цитата
Да тут не по Hiasm нужен учебник, а по чтению... В задаче сказано - перевести число из римской записи в обычную, а уже 2 человека поняли наоборот.
карма: 1

0
Ответов: 16884
Рейтинг: 1239
#12: 2008-02-09 17:42:13 ЛС | профиль | цитата
nesco,
99 = IC
499 = ID
999 = IM
1999 = MIM
3999 = MMMIM

карма: 25
Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!
0
Ответов: 899
Рейтинг: 43
#13: 2008-02-09 18:01:11 ЛС | профиль | цитата
Про коров задачка интересная
карма: 0
Время верстки: %cr_time% Текущее время: %time%
0
Разработчик
Ответов: 26061
Рейтинг: 2120
#14: 2008-02-09 18:10:14 ЛС | профиль | цитата
Tad, алгоритм не мой, алгоритм стандартный, а это можно вставить как исключение, это -- приколы 9-к. А ты еще и 49 забыл
карма: 22

0
Ответов: 16884
Рейтинг: 1239
#15: 2008-02-09 18:31:52 ЛС | профиль | цитата
nesco писал(а):
алгоритм не мой, алгоритм стандартный
значит он неправильный.
И что римляне считали только до 3999?
Тысячу можно было написать и буквой "М" и буквой "I" с горизонтальной линией сверху.
А "XL" с горизонтальной линией сверху - это уже 40 000.
карма: 25
Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!
0
Сообщение
...
Прикрепленные файлы
(файлы не залиты)