Реализация задачки с собеседования: найти максимальное число, но не более, чем ограничено параметром

31.03.22

Разработка - Математика и алгоритмы

Реализация небольшой задачки с собеседования: найти максимальное число в матрице чисел размерностью M*N, заполненной случайными числами, но не большее, чем задано ограничивающим параметром. Сразу скажу, это не с моего собеседования. Просто интересно было решить ее на платформе 1С.

Скачать файлы

Наименование Файл Версия Размер
Реализация задачки с собеседования: найти максимальное число, но не более, чем ограничено параметром.:
.epf 8,86Kb
0
.epf 8,86Kb Скачать

Заинтересовала небольшая теоретическая задачка на алгоритмизацию и работу с матрицами (читай циклами). И захотелось реализовать ее на языке 1С. Заодно вспомнить основы работы с сортировкой. 

Используемая версия платформы 8.3.18.1336.

Решила написать внешнюю обработку и весь код сделать в модуле формы.

Добавила реквизиты: Размерность матрицы, диапазон заполнения: верхняя и нижняя границы и поле ввода для ограничивающего параметра.

Кнопка "Сгенерировать" для генерации матрицы по заданным условиям. И кнопка "Найти число" для поиска первого удовлетворяющего заданным условиям числа.

 

 

Ничего хитрого тут нет. Все операции проводятся на серверной стороне. 

1. СгенерироватьНаСервере()

&НаСервере
Процедура СгенерироватьНаСервере()
	ТЗМодуль = Новый ТаблицаЗначений;
	х = 0;
	у = 0;
	ИмяКолонки = "";
	
	// Создание пустой ТЗ размером М*Н
	ОписаниеСтроки = Новый ОписаниеТипов("Строка", Новый КвалификаторыСтроки(10));
	Пока х < ЧислоСтолбцов Цикл
		ИмяКолонки = "л"+х+"";
		ТЗМодуль.Колонки.Добавить(ИмяКолонки, ОписаниеСтроки);
		х = х + 1;
	КонецЦикла;
	Пока у < ЧислоСтрок Цикл	
		ТЗМодуль.Добавить();
		у = у + 1;
	КонецЦикла;
	
	// Заполнение ТЗ случайными числами
	ГСЧ = Новый ГенераторСлучайныхЧисел();
	х = 0;
	у = 0;
	Пока х < ЧислоСтрок Цикл
		Пока у < ЧислоСтолбцов Цикл	
			ТЗМодуль[х][у] = ГСЧ.СлучайноеЧисло(НижняяГраница, ВерхняяГраница);
			у = у + 1;
		КонецЦикла;
		у = 0;
		х = х + 1;
	КонецЦикла;
	
	
	Для Каждого Колонка Из ТЗМодуль.Колонки Цикл
		Инфо = Инфо + " " +Колонка.Имя+ " Тип значения: " +Колонка.ТипЗначения + ". "; 
	КонецЦикла;
	
	// Собирается инофрмация по добавленным ранее элементам формы и реквизитам, на которые элементы формы ссылаются.
	УдаляемыеРеквизиты = Новый Массив;
	УдаляемыеЭлементы = Новый Массив;
	Для каждого Эл Из Элементы.ТЗ.ПодчиненныеЭлементы Цикл
		УдаляемыеРеквизиты.Добавить(Эл.ПутьКДанным);
		УдаляемыеЭлементы.Добавить(Эл);
	КонецЦикла; 
	Для каждого Эл Из УдаляемыеЭлементы Цикл
		Элементы.Удалить(Эл);
	КонецЦикла; 

	// Добавляются колонки из ТаблицыЗначений ТЗМодуль в реквизит формы ТЗ
	НовыеРеквизиты = Новый Массив;
	Для Каждого Колонка Из ТЗМодуль.Колонки Цикл
		НовыйРеквизит = Новый РеквизитФормы(Колонка.Имя, Колонка.ТипЗначения, "ТЗ", Колонка.Заголовок);
	   	НовыеРеквизиты.Добавить(НовыйРеквизит);
	КонецЦикла;
	
	//Удаляются старые и устанавливаются новые реквизиты
	ИзменитьРеквизиты(НовыеРеквизиты, УдаляемыеРеквизиты);
	
	// Динамически добавить на форму элемент формы ТЗ со всеми колонками
	// Добавляются колонки из ТаблицыЗначений в элементы ТабЭлементФормы со ссылкой на колонки в ТабРеквизит
    Для Каждого Колонка Из ТЗМодуль.Колонки Цикл
        НовыйЭлемент = Элементы.Добавить(Колонка.Имя, Тип("ПолеФормы"), Элементы.ТЗ);
        НовыйЭлемент.Вид = ВидПоляФормы.ПолеВвода; //Или ПолеВвода, или что-то другое;
		ПутьКДанным = "ТЗ." + Колонка.Имя;
		НовыйЭлемент.ПутьКДанным = ПутьКДанным;
    КонецЦикла;
	
 	// В созданный реквизит загружается ТЗ
	ЗначениеВРеквизитФормы(ТЗМодуль, "ТЗ");

КонецПроцедуры

Здесь сначала происходит создание пустой таблицы значений. с описанием типов для колонок. Потом заполнение таблицы случайными значениями через объект встроенного языка ГенераторСлучайныхЧисел().

Потом динамически добавляем на форму колонки для таблицы значений. Вызываем стандартную процедуру глобального контекста ИзменитьРеквизиты().  

И вторая команда: Найти число. Здесь происходит поиск первого наибольшего числа, но не большего, чем задано в ограничении. 

&НаСервере
Процедура НайтиЧислоНаСервере()
	ТЗРасчет = РеквизитФормыВЗначение("ТЗ");
	х = 0;
	у = 0;
	к = 0;
	СчетчикИзмененияК = 0;
	
	МассивПодходящихЧисел = Новый Массив();
	МассивКоординатНайденных = Новый Массив();
	МассивКоординатНайденных.Добавить(Новый Массив());
	МассивКоординатНайденных.Добавить(Новый Массив());
	// 1. найти, а есть ли вообще хоть одно число, удовлетворяющее условию?
	Пока х < ЧислоСтрок Цикл
		Пока у < ЧислоСтолбцов Цикл	
			 
			Если Число(ТЗРасчет[х][у]) < МеньшеЭтогоЧисла Тогда
				 к = Число(ТЗРасчет[х][у]);
				 МассивПодходящихЧисел.Добавить(к);
				 МассивКоординатНайденных[0].Добавить(х);
				 МассивКоординатНайденных[1].Добавить(у);
				 СчетчикИзмененияК = СчетчикИзмененияК + 1;
			Иначе
				//
			КонецЕсли;
			у = у + 1;
		КонецЦикла;
		у = 0;
		х = х + 1;
	КонецЦикла;
	
	Если СчетчикИзмененияК > 0 Тогда
		Результат = к;
	Иначе
		Результат = "Нет числа, удовлетворяющего условию."
	КонецЕсли;
	
	// 2. Имея массив отобранных чисел, надо найти максимальный элемент в массиве.
	// Если такое число вообще есть
	Если Результат <> "Нет числа, удовлетворяющего условию." Тогда
		х = 0;
		ПоследняяПозицияИзмененияК = 0;
		ЗнакПредыдущегоШага = NULL;
		ЗнакТекущегоШага = NULL;		
		МахЭлемент = МассивПодходящихЧисел[0];
		Пока х < МассивПодходящихЧисел.Количество() Цикл
			Если МахЭлемент < МассивПодходящихЧисел[х] Тогда
				МахЭлемент = МассивПодходящихЧисел[х];
				ПоследняяПозицияИзмененияК = ПоследняяПозицияИзмененияК + 1; 
				ЗнакТекущегоШага = ИСТИНА;
			Иначе
				ЗнакТекущегоШага = ЛОЖЬ;	
			КонецЕсли;
			х = х + 1;
		КонецЦикла;
		Результат = МахЭлемент;
	Иначе
		// 	
	КонецЕсли;
	
	
КонецПроцедуры

 

задача матрица сортировка динамическая генерация таблица

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1753    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4415    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7450    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7848    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4443    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8830    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7796    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. RustIG 1351 31.03.22 10:47 Сейчас в теме
(0) для визуальной наглядности можно создать служебную колонку со значениями в строках у0, у1, у2 ...
2. RustIG 1351 31.03.22 10:49 Сейчас в теме
(0) я так понимаю - здесь нужно использовать полный перебор всех чисел...не частичный , а именно полный - чтобы найти все максимальные (одинаковые например) значения
3. RustIG 1351 31.03.22 10:51 Сейчас в теме
(0) Выражение "первого" удовлетворяющего условию - не раскрыто - первый слева направо сверху вниз?
матрицу можно обходить сначала берем первый столбец - обходим все строки, затем берем второй столбец - обходим все строки....
4. RustIG 1351 31.03.22 10:52 Сейчас в теме
(0) для визуальной проверки не хватает вывода номеров ячеек, в которых найдены максимальные числа
serverstar; +1 Ответить
12. serverstar 62 18.04.22 16:52 Сейчас в теме
(4) согласна, это необходимо сделать
5. RustIG 1351 31.03.22 10:54 Сейчас в теме
(0) почему-то не используете встроенную функцию Макс(Число1, Число2) ?
6. RustIG 1351 31.03.22 10:57 Сейчас в теме
(0) на картинке нижняя и верхняя граница 150 и 25 - непонятно почему не наоборот?
7. RustIG 1351 31.03.22 11:01 Сейчас в теме
(0) у вас используется три цикла, хотя можно использовать всего два цикла - внутри цикла в цикле делать все проверки на макс и ограничение...
8. sapervodichka 6697 31.03.22 11:56 Сейчас в теме
мне кажется нужно просто
1) Поместить ТЗ в массив
2) Отсортировать массив по возрастанию;
3) Пройти массив от первого элемента до конца и взять элемент максимально близкий к заданному при выполнении условия ЭлМассива[i] <= ЗаданныйКритерий И ЭлМассива[i+1] > ЗаданныйКритерий.
serverstar; +1 Ответить
13. serverstar 62 18.04.22 16:54 Сейчас в теме
(8) можно и так. ваш вариант проще. но мне захотелось так
15. sapervodichka 6697 18.04.22 17:17 Сейчас в теме
(13) не у меня так, мимо ))) проще ниже ))) у SlavaKron
9. SlavaKron 31.03.22 12:16 Сейчас в теме
МаксимальноеЧисло = Неопределено;

Для Каждого Стр Из ТЗРасчет Цикл
	Для Каждого Значение Из Стр Цикл
		Если Значение < МеньшеЭтогоЧисла И (МаксимальноеЧисло = Неопределено ИЛИ Значение > МаксимальноеЧисло) Тогда
			МаксимальноеЧисло = Значение;
		КонецЕсли;
	КонецЦикла;
КонецЦикла;

Возврат МаксимальноеЧисло
Показать
avbolshakov; rpgshnik; DrAku1a; sapervodichka; +4 Ответить
10. serpent 67 31.03.22 18:20 Сейчас в теме
А почему на первом скрине "результат" = 98. Такого числа вроде нет в массиве. Или я что-то не так понял?
11. FractonKireyev 18.04.22 15:48 Сейчас в теме
За такое решение задачи я бы посоветовал не заниматься программированием вообще.
Ну не Ваше это.
Mikeware; +1 Ответить
14. serverstar 62 18.04.22 16:58 Сейчас в теме
(11) знаете, опыт приходит с ошибками. и кто ничего не делает, тот не ошибается.

для того я и показала свою реализацию. да, я знаю что она в чем-то громоздкая.
но почитав советы более опытных коллег, я пойму, в чем мои действия были неоптимальными
TokarevV; Aleksey3A; Maxim_Zuev; +3 Ответить
16. Said-We 01.02.24 14:41 Сейчас в теме
(1) (15) Нее... так скучно. Часто на собеседовании задача иная в ней значения в матрице отсортированы по возрастанию и в строках и в колонках - самые маленькие в верхнем левом углу, максимальные в нижнем правом углу. Числа не повторяются. Необходимо за меньшее количество итераций найти в списке искомое число если оно есть. Количество колонок и строк в матрице известно.
Оставьте свое сообщение