1 Вопрос: "Ход конём" см. комментарий (42) ... Решения: (49)
2 Вопрос: "Найдите кратчайший путь коня между двумя заданными клетками на шахматной доске." см. комментарий (76) Решения: (98)
3. Вопрос: Найти максимальное вхождение. см. комментарий (107)
Благодарность за финансовую (стартмани) поддержку проекта anig99, AnryMc, DitriX, juntatalor, Bukaska, alexk-is, poligraff !
Конкурс:
1. Задайте "лучший вопрос" по 1С
2. Ответьте на "лучший вопрос"
Ответ должен быть оформлен в виде обработки.
Обработку выствить в своих "Публикациях" указать ссылку на данный "Конкурс", здесь указать ссылку на свою "публикацию".
с уважением "Шёпот теней" в миру Александр Шишкин ...
Вообще тема интересная.
Я например люблю лазить вот сюда http://www.braingames.ru/ и тут ломать свой моск.
Вот например одна клевая задачка оттуда:
Как поменять местами значения двух числовых переменных без использования дополнительных переменных и/или памяти? В используемом языке нет оператора обмена значениями (вроде XCHG ассемблера).
(61) хе. Ну это уровень детского сада.
А вот такую задачку:
Шли два мегамозга, работающие малярами, навстречу — еще двое. У каждого руки испачканы своей краской, и никому не хочется пачкаться чужой. Мегамозги хотят поздороваться друг с другом (каждый из первой пары с каждым из второй и наоборот) рукопожатием, но на всех есть только две перчатки. Как им можно решить эту проблему? Перчатки не выворачиваются.
(62) DitriX, Ответ очевиден - никак, т.к. в перчатках нормальные мужики не здороваются, считается плохим тоном. Только девушки здороваются, но это не является обязательным. Вариант - запястьем поздороваться или тем, что не испачкано. Можно просто зигу кинуть, хе :))
Ну как же, мне казалось это очевидным.
Сначала один здоровается с двумя (у перчатки две стороны), затем перчатка снимается и надевается на руку второго (внешняя перчатка внутри чистая, но имеет снаружи цвета встречных) и он здоровается с встречными повторно перчаткой с цветами встречных.
Подражая ШТ ... ВоТ гДе тО таК... я ... я так думаю.
цветов краски всего два? "У каждого руки испачканы своей краской" - или четыре?
если всего два цвета, то одна пара мегамозгов(с одним цветом) надевает перчатки и здоровается с другой парой по очереди...
(68) GalinaK, Есть такая система- СИ. Что бы считать корень из рубля, надо ещё понять, а какой в этом физический смысл? :)
Единицы измерения так не переводят.
Задача 2: Найдите кратчайший путь коня между двумя заданными клетками на шахматной доске.
Программа должна вывести кратчайший путь коня, начинающийся и заканчивающийся в данных точках. Необходимо вывести все клетки, через которые проходит конь в порядке прохождения. Если коротких маршрутов несколько необходимо вывести все возможные.
(76) Вот мое решение (прилагается обработка). Всего 30 строк. Перечисляются все кратчайшие пути.
Функция Спираль(А, Б, Круг = 0)Экспорт
Поле = НоваяТаблицаЗначений("Х, У, Круг, Связи");
Для К = 0 По 63 Цикл
ЗаполнитьЗначенияСвойств(Поле.Добавить(), Новый Структура("Х, У, Круг, Связи", Цел(К / 8), К % 8, (К = А) - 1, Новый Массив))
КонецЦикла;
Пока Поле[Б].Круг < 0 Цикл
Целина = Поле.НайтиСтроки(Новый Структура("Круг", -1));
Трек = Поле.НайтиСтроки(Новый Структура("Круг", Круг));
Для Каждого С Из Целина Цикл
Для Каждого К Из Трек Цикл
Если (С.Х - К.Х) * (С.Х - К.Х) + (С.У - К.У) * (С.У - К.У) = 5 Тогда
С.Круг = Круг + 1;
С.Связи.Добавить(К.Х * 8 + К.У)
КонецЕсли
КонецЦикла
КонецЦикла;
Круг = Круг + 1
КонецЦикла;
Возврат Поле
КонецФункции
Процедура Спуск(Б, Поле, Знач Путь = "") Экспорт
Путь = Сред("abcdefgh", Б / 8 + 1, 1) + (Б % 8 + 1) + " " + Путь;
Если Поле[Б].Связи.Количество() = 0 Тогда
ЗаполнитьЗначенияСвойств(Пути.Добавить(), Новый Структура("Путь", Путь))
Иначе
Для Каждого К Из Поле[Б].Связи Цикл
Спуск(К, Поле, Путь)
КонецЦикла
КонецЕсли
КонецПроцедуры
Показать
Первая функция размечает доску, вторая рекурсивно перечисляет пути из конечной точки.
Разметка идет "по спирали". Номер витка (круга) соответствует минимальному расстоянию от начальной точки. На каждом витке неразмеченные клетки просматриваются в паре с каждой клеткой последнего витка. Если расстояние (сумма квадратов разности координат равно пяти) соответствует шагу коня клетка включается в следующий виток (круг). И так пока в круг не попадет конечная клетка. В каждой клетке запоминается массив клеток предыдущего витка, из которых попадают в текущую. Это дает возможность рекурсивно раскрутить пути до начальной точке "при спуске".
В отличие от предыдущего решения здесь не строится граф и не сортируются пути, так как это излишне в данной задаче.
п.с.0. не видно количество и пути правильных ходов ... укажите координаты доски, непонятно как считать, что смотреть ... Например где "цифры" и "буквы" ?
У Шахматной доски отсчёт начинается с нижнего левого угла и он чёрный ...
п.с.1. минимализация хорошо но хочется и наглядности ...
Сделал обработку. Единственное пока отображается только 1 самый короткий маршрут.
Добавил от себя несколько фишек:
1.Произвольный размер поля
2.Вычисление на каждом шаге расстояния, которое осталось преодолеть коню :)
Вот блин. Действительно.. Оказывается дойти до этой клетки можно. Да уж, жаль нет под рукой шахматного поля. Оказывается метод постоянного максимально приближения к цели не катит, по крайней мере когда конечная точка близка..
требуется оптимизация в виде запомниная ходов, чтобы не повторять ходы несколько раз как удачные так и неудачные(ходов на самом деле не очень много) ...
нужна помощь в обработке ход конем. хочу понять как делать. но не знаю с чего начать. я начинающий программист. если у нет желания помочь. не прошу решить. а помочь. хочу разобраться и понять.
(87)
1. начните с первого задания см.(42)
2. почитайте в инете ... там есть решения некоторых задач с описанием как математически описать шахматную доску и другие физические обЪекты
... вот ...
п.с. ничего сложного нет ... например тут: http://is.ifmo.ru/?i0=works&i1=knight ... вопрос только знаний языков программирования ... но и теоритеческие знания то же помогут !
хочу сам разобраться - это для тех кто хочет написать никто тебе решать не будет.
нужны советы с чего начать и т.д.
нужна помощь, потому что не занимался таким. не просто хочу механически все сделать, а и во всем разобраться.
стока умников развилось. те не хотят помочь, те рисуй и разбирайся.... куча советов и замечаний. но ни от одного толку.
(89) max210, Ну изначально здесь надо инициализировать поле. Шахматную доску можно представить в виде двумерной матрицы 8 на 8. Но я для описания шахматного поля просто создал две переменных Xmax и Ymax, по-умолчанию значения этих переменных равны 8, но можно и изменить, если хочется нестандартное поле.
После чего надо создать ещё один массив, где мы опишем возможные ходы конём. Я это делал таким образом:
ТЗ = Новый ТаблицаЗначений;
ТЗ.Колонки.Добавить("hodX", Новый ОписаниеТипов("Число"));
ТЗ.Колонки.Добавить("hodY", Новый ОписаниеТипов("Число"));
Стр = ТЗ.Добавить();
Стр.hodX = 2;
Стр.hodY = 1;
Стр = ТЗ.Добавить();
Стр.hodX = -2;
Стр.hodY = 1;
Стр = ТЗ.Добавить();
Стр.hodX = 2;
Стр.hodY = -1;
Стр = ТЗ.Добавить();
Стр.hodX = -2;
Стр.hodY = -1;
Стр = ТЗ.Добавить();
Стр.hodX = 1;
Стр.hodY = 2;
Стр = ТЗ.Добавить();
Стр.hodX = 1;
Стр.hodY = -2;
Стр = ТЗ.Добавить();
Стр.hodX = -1;
Стр.hodY = 2;
Стр = ТЗ.Добавить();
Стр.hodX = -1;
Стр.hodY = -2;
Ну тут вариатов много.
Стр.hodX = 2;
Стр.hodY = 1; - означает что конь может передвинуться по координате x на 2 клетки и по координате y на 1 клетку.
Начальные координаты и конечные я представляю в виде 2 пар переменных:
Координата1_X
Координата2_X
Координата1_Y
Координата2_Y
После заполнения пользователем начальных данных, надо выполнить некоторые проверки на корректность.
Если Xmax < 1 или Ymax < 1 Тогда
Сообщить("Недопустимый размер поля");
КонецЕсли;
Если (Координата1_X < 1 или Координата1_X > Xmax) или (Координата1_Y < 1 или Координата1_Y > Ymax) Тогда
Сообщить("Недопустимое координаты точки начала")
КонецЕсли;
Если (Координата2_X < 1 или Координата2_X > Xmax) или (Координата2_Y < 1 или Координата2_Y > Ymax) Тогда
Сообщить("Недопустимое координаты точки конца")
КонецЕсли;
Дальше нам необходимо создать таблицу значений, в которой мы будем записывать ходы.
ТЗХоды = Новый ТаблицаЗначений;
ТЗХоды.Колонки.Добавить("X1", Новый ОписаниеТипов("Число")); - до хода
ТЗХоды.Колонки.Добавить("X2", Новый ОписаниеТипов("Число")); - после хода
ТЗХоды.Колонки.Добавить("Y1", Новый ОписаниеТипов("Число")); - до хода
ТЗХоды.Колонки.Добавить("Y2", Новый ОписаниеТипов("Число")); - после хода
ТЗХоды.Колонки.Добавить("РасстояниеДоЦели", Новый ОписаниеТипов("Число", Новый КвалификаторыЧисла(15,4))); - это просто было сделано для наглядности.
Как я понял ещё нужна таблица значений где будем записывать запрещенные ходы:
ЗапрещенныеХоды = Новый ТаблицаЗначений;
ЗапрещенныеХоды.Колонки.Добавить("X1", Новый ОписаниеТипов("Число"));
ЗапрещенныеХоды.Колонки.Добавить("X2", Новый ОписаниеТипов("Число"));
ЗапрещенныеХоды.Колонки.Добавить("Y1", Новый ОписаниеТипов("Число"));
ЗапрещенныеХоды.Колонки.Добавить("Y2", Новый ОписаниеТипов("Число"));
Вот функции, которые могут пригодиться:
Функция МодульЧисла(Число)
Попытка
Корень=sqrt(Число);
Возврат Число;
Исключение
Возврат -Число;
КонецПопытки;
КонецФункции
Функция Растояние(X1,X2,Y1,Y2)
Возврат Sqrt(((X2 - X1)*(X2-X1)) + ((Y2-Y1)*(Y2-Y1))) ;
КонецФункции
Вот собственно начальные данные у нас есть. А теперь с этим надо плясать. Я сам пока ещё не придумал как сделать лучше. Когда будет доделано выложу код.
Надо не забыть проверить расположение коня, например, из углового поля возможно только два хода, с третьей по шестую клетку крайних линий и вертикалей только 4 хода, со 2 и 7 клеток крайних линий и вертикалей только 3 хода, это для доски 8*8.
Да, это обязательно надо проверять )
Если (ВремКоординатаX + ТЗ[Шаг].hodX < 1 или ВремКоординатаX + ТЗ[Шаг].hodX > Xmax) или (ВремКоординатаY + ТЗ[Шаг].hodY < 1 или ВремКоординатаY + ТЗ[Шаг].hodY > Ymax) Тогда Продолжить;
у меня сейчас сложность состоит в поиске оптимального пути, когда допустим Начальная точка имеет координаты (1,1), а конечная имеет координаты (1,2); Мозги взрываются.
Рабочий день выдался спокойным, и я с большим удовольствием занялся решением задачи - пришлось и почитать, и головой поработать, но в целом результатом я доволен. В счет конкурса отчислил немного SM - думаю, надо поощрять такую инициативу.
Не сразу я пришел к версии с графом и Дейкстрой, сначала "шел своим путем". Путь оказался крайне не оптимальным, и в голове вспомнился университетский курс теории графов. Они тут как нельзя кстати!
Также отмечу, что с выбранной системой исчисления теоретически, нет ограничений на размеры поля.
Чтобы делать поле больше, надо всего лишь скорректировать запрос, ту группу где добавляются "Цифры" (т.е. туда можно добавить и любые последовательно идущие числа)
С другой стороны, было бы неплохо задавать размеры поля полями на форме.
(110)Зачем? Слова разделены знаком препинания и/или пробелом. Их и отлавливать.
Или если вчитаться в условие то после выполнения п.1 будет одна большая строка, тогда это ее длина и будет. :)
Хотя это могут быть и просто строки, тогда нужна максимальная длина строки.
Сколько должно быть максимальных сочетаний? Например, сочетание "Выпьем" длиннее чем сочетание "ружка"! Или максимальные сочетания начинаются от определенного количества букв? Что считать максимальным сочетанием?
З.Ы. И ещё... "Выпьем" и "выпьем" - это разные сочетания или одинаковые? (Имеет ли значение регистр?)
(113) видимо, перед стартом алгоритма нужно указывать минимальную длину цепочки символов - т.е. например минимальной может быть длина 1, тогда мы просто получим частоту встречаемости символов. (если я верно понял условия задачи)
Предложу почитать в эту публикацию http://infostart.ru/public/90367/ , главу про нахождения количества слов в тексте. Думаю, можно задуматься над использованием запросов для решения этой задачи.
(117) juntatalor, нахождение слов в тексте и нахождение последовательностей - несколько разные задачи. Чтобы найти количество слов, достаточно оставить по одному пробелу между словами и посчитать количество пробелов+1
ух, классная тема, классные задачи )) жаль, моих знаний пока не хватает чтобы их осилить, но реально пасиба ^_^ давно искал нечто такое, над чем можно подумать.
Я кое-что набросал, по поводу задачи из поста 107. Мой алгоритм находит строку:
"выпьемдобраяподружкабеднойюностимоейвыпьемсгорягдежекружкасердцубудетвеселей".
При этом я двигаюсь от больших комбинаций к меньшим. Вопрос: после нахождения одной такой комбинации нужно остановиться... Или продолжать поиск дальше (при условии что я точно знаю, что остальные комбинации будут короче уже найденной). Если продолжать, то нужно ли исключить из поиска уже найденный кусок?
(126) ... непонятно по какому "тексту" работает обработка ... и где смотреть результаты? то ли в "окне сообщений" , то ли в обработке - она пустая .. ?
А этот вариант сначала исключает подпоследовательности уже найденных последовательностей, а на случай если вдруг в найденных подпоследовательностях есть тоже повторения, их он тоже ищет
p.s. на мой взгляд наиболее правильный данный вариант
На электронном будильнике табло отображает за сутки числа от 00 до 23. Определите, сколько раз при отображении часов в сутки (минуты не учитываются) используется цифра 1?
Вот такая задача:
Входные данные - строка.
Примеры входных данных:
1) "1,4,6,8,11,14" ,
2) "1-3,5,7,11-23,24,27"
3) "1-99"
Выходные данные - число (количество цифр в последовательности).
В 1 случае результат будет 6.
Во 2 случае - 19
В 3 случае - 99
Строка = Элемент.Значение; // присваиваем строке значение из поля ввода
Строка = СокрЛП(Строка);
Строка = СтрЗаменить(Строка, ",", Символы.ПС); //Запятые заменяем на символы переноса строки
НомерСтроки = 1;
Сч = 0;
Кол = СтрЧислоСтрок(Строка);
// Бегаем по всем строкам
Пока НомерСтроки <= Кол Цикл
ВремСтрока_1 = СтрПолучитьСтроку(Строка, НомерСтроки); // Получаем строку
ВремСтрока_2 = ВремСтрока_1; //копируем
ВремСтрока_2 = СтрЗаменить(ВремСтрока_1, "-", "-0-" ); //Заменяем "-" на "-0-" =)
//Если строки по-прежнему равны, заменяем то что в строке на 1
Если ВремСтрока_1 = ВремСтрока_2 Тогда
ВремСтрока_1 = СтрЗаменить(ВремСтрока_1, ВремСтрока_1, "1");
//иначе считаем выражение в строке
Иначе
Попытка
ВремСтрока_1 = СтрЗаменить(ВремСтрока_1, ВремСтрока_1, Вычислить("-1*(" + ВремСтрока_2 + ")+1"));
Исключение
Сообщить("Неверное выражение", СтатусСообщения.Важное);
Возврат;
КонецПопытки;
КонецЕсли;
// суммируем числа в каждой строке
Попытка
Сч = Сч + (Число(ВремСтрока_1));
Исключение
Сообщить("Неверное выражение", СтатусСообщения.Важное);
Возврат;
КонецПопытки;
НомерСтроки = НомерСтроки + 1;
КонецЦикла;
// Получаем количество различных цифр
Сообщить(Сч);
Задача по нахождению структуры в неупорядоченных данных.
Упорядочить данные по лучшей кратности одинаковых элементов. ***
Лучшая кратность строки = максимальная частотность элемента данных с минимумом пустышек.
Можно использовать совместимый критерий "наилучшести", типа средней плотности/насыщенности строки.
Совместимый = дающий те же результаты, либо (при различии) объективно показательней.
Объективность показательности аргументируется произвольно.
В общем, см. образец решения, так будет понятнее.
Строка на входе: "9,1,2,3,4,1,6,5,2,3,8,4,1,2,3,4,4,1,5,2,3,4".
Строка на выходе:
"9,1,0,0,2,3,0,4,
|0,1,6,5,2,3,8,4,
|0,1,0,0,2,3,4,4,
|0,1,0,5,2,3,0,4"
Принцип расстановки:
1,2 и 3 встречаются по 4 раза, тогда как остальные меньше раз (1-3)*.
5 в последней строке "стоит под" 5 во второй строке, ибо элемент одинаковый (5=5), а 4 в "столбце четвёрок".
Данные нельзя переставлять местами: задача сводится к тому, что нужно лишь дополнить пустышки (0).
*4-ка повторяется 5 раз, но такая расстановка даст больше пустышек:
"...
...
|0,1,0,0,2,3,0,4,
|0,0,0,0,0,0,0,4,
|0,1,0,5,2,3,0,4"
PS: Задача "придумана" мной исходя из практических соображений.
PPS: В исходной строке (для упрощения) указаны цифры, но работать с ними надо как с текстом различной длины.
(151) Решение – заготовка для универсального парсера списков любого рода: форумов, досок объявлений, каталогов, различных лент. Также, может быть применено для поиска различий данных в однотипных "неизвестных" структурах. То же можно проделать разбором схемы вручную, но тут предлагается отдать по-максимуму на откуп искусственному интеллекту.
Фишка с пустышками в том, чтобы выявить "гуляющие" данные, т.е. которые в структуре есть, но проявляются себя непостоянно, необязательно дочерние к основным элементам и могут быть составными. А т.к. данные собираются частично и динамически, то для этого лучше иметь гибридную структуру, автоподстраивающуюся под обстоятельства и непременные будущие переструктуризации.
Я сделал решение на VB упрощенной задачи, - без выравнивания подструктур, - только костяк. Плюс, вместо лучшей кратности, выбор любой одной или нескольких кратностей опционально. Вот подумал, в 1С такое замутить тоже было бы неплохо, тем более для Конкурса годное задание. А поскольку упрощенное решение сводится к: выбрать уникальные, посчитать, снова уникальные, сортировать и форматировать, то, ввиду (147), доформулировал задачу для интереса и более качественного ИИ.
Тем самым, можно подойти к решению разными способами: на основе решения в лоб рекурсией, конечным автоматом, тупо брутфорсом по ограниченной выборке, либо какой-нибудь хитрой комбинаторикой. В общем, возможность пошуршать винтиками и придумать какой-то индивидуальный подход к решению.
PS: Для полноценного парсера нужны ещё: граббер, шаблоны каркасов, автофильтры, выявление принадлежностей, типизация, моделирование, межресурсные связи и прочее. Для сопоставлятора - в зависимости от объекта сравнения: документы на естественном языке, сериализованные объекты или анкетные формы, - для каждого свои способы. Но это уже другая история.
Шаг3. Если подстрока максимум из 1 элемента, разворачиваем:
{9123}4-1{65}2384
{123} 441{5} 23-4
Шаг4. Повторяем шаги 1-3 для каждой оставшейся подстроки:
9123/123 → 9123/-123
65/5 → 65/-5
Шаг5. Соединяем:
91234-1652384
-123441-523-4
PS: Пробелы в строке - для красоты отображения на форуме, в промежуточном решении их нет. Выделение подстрок скобками - схематично, по факту их хранение (выделение) произвольное.
Ставлю клиентам УТ.
Бабулька бухгалтер спрашивает: "Как бы мне моих 1500 контрагентов перетянуть из ОПЗ???" (для тех кто не знает- ОПЗ-програмне забезпечення по формуванню та подачі платниками податків податкової звітності та реєстру отриманих та виданих податкових накладних до органів ДПС в електронному вигляді засобами телекомунікаційного зв'язку - редкая гадость, но иногда выручает)
Вот такая задача.
P.S. Бабулек ведущих выписку первички в ОПЗ я встречал всего два раза.
(154) AnryMc,
Послушайте, уважаемый, человек TODD22 (готовый за деньги все отдать, продать) мне задал вопрос-претензию что мол я больших денег не видел. Я ему ответил. Т.к. по роду работы очень часто приходится видеть большие деньги. Как то было видел (стоял рядом, трогал руками) приблизительно кубический метр денег. Зрелище впечатляет.
Вам я смотрю это как то не дает покоя. Что не нравится?
Типа:
- Почему на болоте нельзя считать деньги?
- Жаба задавит?!
По поводу поста. Ну значит я не правильно понял что значит "Лучший вопрос - Лучший ответ".
Мой пост - это вопрос.
Дайте ответ!
У меня на решение вопроса пошло мин 15.
Ну так почему Вы мне этими коробками, уже не первый раз отвечаете!?
Обычно говорят о "дипломатах" (в крайнем случае - кульках) а тут коробки из под бумаги А4 - Свежо!
Это просто фраза. Пустышка.
Конкретизируйте, обоснуйте 2 мин.
Затенуть из .xml 5-ть полей
id name
HK Індивідуальний податковий номер
HNAME Назва (Прізвище, ім'я, по-батькові)
HLOC Місцезнаходження
HTEL Номер телефона
HNSPDV Номер свідоцтва ПДВ
(158) AnryMc,
Затянуть 5 полей из .xml - 99% пользователям сайта это будет понятно.
А вот бабулька 60 лет. Для нее даже .xml - это ребус.
Чем затянуть?
В этом пути коня между клетками отсутствует большая часть клеток.
Дополнительные исходные данные.
1.Комп без интернета.
2.Флешки все забыл дома.
3.В наличии только коробка с УТ.