На Infostart уже было несколько статей, посвященных платформе для решения задач на языке 1С. Я хочу разобрать задачу, которая входит в сборник заданий и называется Плитки шоколада. Условие следующее.
Шоколадная фабрика производит необычный шоколад.Плитки шоколада выпускаются в виде длинных плиток 1 × N, состоящих из N квадратов.На каждом квадрате изображен портрет одного из N известных кондитеров этой компании.На разных плитках шоколада изображены одни и те же портреты N кондитеров, но в разном порядке.Задача:Напишите функцию, которая для заданного порядка портретов двух плиток шоколада определяет минимальное количество разломов,которое нужно выполнить на первой плитке, чтобы сформировать вторую плитку, переставив сломанные части.Дано:Первая, Вторая - строка, описывающая каждую из плиток шоколада.Состоит из массива целых чисел от 1 до N, разделенных запятой. Каждое число уникально, оно обозначает соответствующего кондитера.Результат:Целое число — минимальное количество разломов, которое нужно выполнить на первой плитке, чтобы сформировать вторую плитку, переставив и соединив сломанные части.Ограничение:Разломать плитку можно только по границам ее квадратов.Переворачивать исходную плитку или ее части нельзя.Порядок кондитеров в первой и второй плитке всегда отличается.2 <= N <= 1000.Пример:Первая = "4,3,2,5,1"Вторая = "1,2,5,3,4"Результат = 3Пояснение: первую плитку нужно разломать 3 раза на части: "1", "2,5", "3", "4".А потом соединить полученные части, чтобы получить вторую плитку.
Проговорим шаги решения. Берем левую ячейку первой плитки и находим одинаковую ячейку во второй плитке. Это можно сделать всегда. Теперь проверяем ячейки справа от найденной ячейки для первой и второй плитки. Двигаемся вправо пока портреты на ячейках совпадают, останавливаемся, когда либо они различаются, либо мы достигли конца одной из плиток. В этот момент мы отламываем часть первой плитки и устанавливаем 0 во все найденные совпадающие ячейки из второй плитки. Увеличиваем счетчик разломов на единицу или заканчиваем наш подсчет, если мы достигли правого края первой плитки. Если край не достигнут, то выполняем все предыдущие действия. Проиллюстрируем это на примере из задания. Начальная конфигурация:
4,3,2,5,1
1,2,5,3,4
счетчик=0
После первого шага:
3,2,5,1
1,2,5,3,0
счетчик=1
После второго шага:
2,5,1
1,2,5,0,0
счетчик=2
После третьего шага:
1
1,0,0,0,0
счетчик=3
Осталась одна плитка, ничего ломать не надо. Алгоритм заканчивается. Ответ:3 Следующий программный код реализует изложенный подход.
Функция ПлиткиШоколада(Первая, Вторая)
Стр1=СтрРазделить(Первая,","); //преобразуем исходные строки в массивы
Стр2=СтрРазделить(Вторая,",");
Стр2.Добавить(0); //ограничительный элемент, чтобы не проверять размер массива Стр1
ответ=0;
пока Стр1.Количество()>0 цикл
б=Стр1[0]; //номер портрета из первой плитки
старт=Стр2.Найти(б); // позиция этого портрета во второй плитке
для i=старт по Стр2.ВГраница() цикл
если Стр2[i]=0 или Стр1[0]<>Стр2[i] тогда
прервать;
иначеесли Стр1[0]=Стр2[i] тогда
Стр1.Удалить(0); //удалим обработанную ячейку из первой плитки, чтобы не делать цикл
Стр2[i]=0; //это можно не делать
конецесли;
конеццикла;
//если в первой плитке остались ячейки добавляем к счетчмку 1
ответ=ответ+(Стр1.Количество()>0); //неявное преобразование булево в число
конеццикла;
возврат ответ;
КонецФункции
Можно поступить немного иначе. Исходные данные - это набор чисел от 1 до N, которые расположены в произвольном порядке. Занесем сведения по второй плитке в массив, где индекс массива это номер ячейки, а значение массива - позиция в массиве, который получается при использовании метода СтрРазделить(...). Ниже приводится соответствующий код.
словарь=новый массив(Вычислить("макс("+Вторая+")")+1);
ном=0;
для каждого запись из СтрРазделить(Вторая,",") цикл
словарь[число(запись)]=ном;
ном=ном+1;
конеццикла;
Размер массива мы получаем с помощью метода Вычислить и функции макс(...). Тогда данные (1,2,5,3,4) из рассмотренного выше примера образуют следующий массив:
словарь[1]=0;
словарь[2]=1;
словарь[5]=2;
словарь[3]=3;
словарь[4]=4;
Теперь пройдемся по массиву ячеек первой плитки.
ответ=-1;пред=ном+2;
для каждого запись из СтрРазделить(Первая,",") цикл
тек=словарь[число(запись)];
если (тек-пред)<>1 тогда
ответ=ответ+1;
конецесли;
пред=тек;
конеццикла;
Заведем две переменные тек и пред. В переменной тек мы получаем позицию в массиве с ячейками второй плитки с номером портрета ячейки из первой плитки. В переменной пред мы храним эту информацию для предыдущей ячейки первой плитки. Если разница между этими переменными не равна 1, мы увеличиваем значение переменной ответ. Для самой первой левой ячейки в переменную пред заносим число заведомо большее размера массива, с которым работаем. Начальное значение переменной ответ делаем равным -1, чтобы не учитывать этот случай. Предложенное решение показывает наилучшее быстродействие среди решений других участников. Надеюсь, что читатели смогли разобраться в изложенном алгоритме.
В заключении хочу порекомендовать всем, кто интересуется спортивным программированием, присоединиться к участникам проекта 1С:Турниры. К настоящему моменту проект содержит более 460 задач различной сложности и позволяет развить навыки работы с объектами и методами языка 1С.
