Каталог решений - Практическое применение операции копирования массива

При обсуждении методов копирования массива возник вопрос о примере практического применения такого механизма. Я использовал данную возможность при решении некоторых задач Project Euler. Так как  участники обсуждения проявили интерес к данной теме, то я счел возможным привести свой алгоритм. Условие задачи следующее. Дан ряд чисел и нужно найти количество подмножеств исходного множества, для которых выполняется условие, что сумма чисел из подмножества делится на заданное число. Во всех задачах на делимость нужно оперировать не с числом, а с остатком от деления. Потому первый шаг решения состоит в поиске остатков от деления исходных чисел на заданное. Все остатки от деления на число n лежат в диапазоне [0,…,n-1]. Поэтому создадим массив размерностью n, индекс массива — остаток от деления, значение — количество  чисел из первоначального множества, которые дают при делении такой остаток. Исходные числа имеют вид x^y поэтому нам понадобится функция для быстрого возведения в степень по модулю.

  Функция БыстраяСтепень(знач x,знач y, знач mode=1) экспорт
  	остаток=y;произведение=1;
  	пока (остаток<>0) цикл
  		цифра=остаток%2;
  		если  цифра=1 тогда
  			если mode=1 тогда
  			 произведение=произведение*x
  		    иначе 
  			 произведение=(произведение*x)%mode
  			конецесли; 
  		конецесли;;	
  		если mode=1 тогда
  		 x=x*x;
  	    иначе
  		 x=(x*x)%mode;  
  		конецесли;; 
  		остаток=(остаток-цифра)/2
  	enddo;	
  	
  	возврат произведение;
  КонецФункции
  

Теперь мы можем заполнить массив с информацией о количестве остатков исходного множества.

  массив=новый  массив(n);
  для i=1 по верх цикл
  		j=БыстраяСтепень(i%n,i,n);
  		если массив[j]=неопределено тогда
  			массив[j]=1;
  		иначе	
  			массив[j]=массив[j]+1;
  		конецесли;	
  конеццикла;	

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

  Функция ПроектЭйлер250(верх,n) экспорт
  	
  		
  	массив=новый  массив(n+1);
  	для i=1 по верх цикл
  		j=БыстраяСтепень(i%n,i,n);
  		если массив[j]=неопределено тогда
  			массив[j]=1;
  		иначе	
  			массив[j]=массив[j]+1;
  		конецесли;;	
  	конеццикла;	
  	
  	mode=БыстраяСтепень(10,16);
  	
  	
  	счетчик=новый  массив(n);
  	для  i=0 по n-1 цикл
  		счетчик[i]=0;
      конеццикла;
  	
  	
  	для остаток=0 to n-1 do
  		если массив[остаток]<>неопределено then
  			для k=1 по массив[остаток] цикл
  				//здесь мы копируем массив счетчик в массив буфер
  			    буфер=новый массив(новый  ФиксированныйМассив(счетчик));	
  				для j=0 по n-1 цикл
  					если счетчик[j]<>0 тогда
  						остаток_суммы=(остаток+j)%n;	
  						буфер[остаток_суммы]=(буфер[остаток_суммы]+счетчик[j])%mode;
  					конецесли;   
  				конеццикла;
  				буфер[остаток]=(буфер[остаток]+1)%mode;
  				счетчик=буфер ;
  			конеццикла;	
  		конецесли;
  	конеццикла;		
  	
  	возврат  счетчик[0];
  КонецФункции	
  

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

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

  Функция РешетоЭратосфена(граница) экспорт
  	
  	решето=новый массив(граница+1);
  	
  	простые_числа=новый массив;
  	для н=2 по граница цикл
  		если решето[н]=неопределено тогда
  			простые_числа.Добавить(н);
  			для к=н по граница цикл
  				если решето[к]=неопределено тогда
  				 решето[к]=1;	
  				иначе	
  				 решето[к]=решето[к]+1;
  				конецесли; 
  				к=к+н-1;
  	        конеццикла;
  		конецесли;
  	конеццикла;	
  	
  	возврат простые_числа;
  КонецФункции	

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

Хочу заранее ответить на вопрос: "Зачем решать такие задачи?". Разумеется, практического смысла в данной деятельности нет никакого. Как нет смысла в  том, чтобы пить вино, курить табак, играть в шахматы и подниматься на Эверест.  Тем не менее, люди занимаются этим веками.