gifts2017

Идеальные квадраты и комплексные числа

Опубликовал Валерий (scientes) в раздел Программирование - Практика программирования

В статье показано, как реализовать в 1С операции с комплексными числами, и приведен пример решения задачи на поиск идеальных квадратов.
 Трудно предположить, что когда-нибудь в бухгалтерском учете понадобятся действия с мнимой единицей. Тем не менее, ничто не мешает нам с помощью средств встроенного языка реализовать операции с комплексными числами.
 Хранить число мы будем в двумерном массиве, в одной ячейке - вещественную часть, в другой - мнимую. Вот и первая функция, которая применяется для создания числа указанного вида.
Function zNumber(Re,Im) Export
   arr=new array();
   arr.Add(Re);
   arr.Add(Im);
   
   return arr;
EndFunction  
В качестве аргументов мы передаем значения вещественной и мнимой части и функция возвращает нам заполненный массив. Теперь реализуем умножение комплексных чисел.
Function zMult(a,b) Export
   arr=new array();
   arr.Add(a[0]*b[0]-a[1]*b[1]);
   arr.Add(a[0]*b[1]+a[1]*b[0]);
   
   return arr;
EndFunction   

Аргументы функции - два комплексных числа, возвращаемое значение двумерный массив. Следующая функция позволяет возвести комплексное число в целую степень. 

Function zPower(z,p) Export
   
   if p=0 then
      arr=new array;
      arr.Add(1);
      arr.Add(0);
      return arr;
   endif;   
   
   if p=1 then
      return z;
   endif;   
   
   if (p%2)=0 then
      t=zPower(z,p/2);
      return zMult(t,t);
   endif;   
   
   return zMult(zPower(z,p-1),z);
EndFunction   

В приведенном коде мы пытаемся сократить требуемое количество операций умножения, заменяя четные степени возведением в квадрат. А вот еще одна элементарная функция, которая возвращает число сопряженное данному.

Function zConjugate(z) Export
   arr=new array();
   arr.Add(z[0]);
   arr.Add(-z[1]);
   
   return arr;
EndFunction   
 Теперь с помощью этого небольшого набора решим задачу нахождения представления числа в виде суммы квадратов.
Вспомним, что согласно основной теореме арифметики любое число можно выразить в виде произведения степеней простых чисел. Представление для простого числа состоит из самого простого числа. Пример простых чисел - 2,3,5,7,11,13... А вот число 65 - составное и оно равно произведению 5 и 13. Оказывается, что греческий математик Диофант, живший в III веке нашей эры, знал, что 65 это минимальное натуральное число, которое можно представить в виде суммы квадратов двумя различными способами
  1. 65=1*1+8*8
  2. 65=4*4+7*7 
Впрочем, греки знали пифагоровы тройки и подобные наблюдения вполне ожидаемы. Интереснее другое, Диофант объяснял подобное свойство числа 65 тем, что оно есть произведение двух чисел и 13, которые в свою очередь, тоже можно выразить как сумму квадратов.Оказывается, среди простых чисел в виде суммы квадратов можно записать только числа вида 4*k+1. В частности:
  • 5 =1*1+2*2
  • 13=2*2+3*3 
Настал момент вспомнить про комплексные числа. Если число можно записать как сумму квадратов, то оно раскладывается на комплексные множители, так 5=(2+i)(2-i), a 13=(3+2i)(3-2i). Группируя комплексные множители в разложении числа 65 различными способами, мы получим два разложения на сумму квадратов. А как нам перебрать все возможные комбинации ? Предлагается следующее решение. Если в разложение входит степень двойки, то она заменяется степенью комплексного числа(1+i), если в разложение входят степени простых чисел вида 4*k+3, то эти степени объединяются в одно число Q, которое записывается в виде (Q+0*i), если в разложение входит степень простого числа вида Z=4*k+1, то оно заменяется массивом комплексных чисел (Z**i)*(Zсопряженное**(p-i)), где i меняется от 0 до p (p - степень данного простого числа в разложении)..
Приведем код функций, которые нам понадобятся для приведенного алгоритма.
Function zGenerateVar(z,p) Export
    arr=new array;
    
    zCon=zConjugate(z);
    arr.Add(zPower(z,p));
    for i=1 to (p-1) do
       arr.Add(zMult(zPower(z,i),zPower(zCon,p-i)));
    enddo;    
    arr.Add(zPower(zCon,p));    
   
    return arr;
EndFunction   

Функция РазложитьНаПростыеМножители(вхЧисло,ПростыеЧисла)
   тЧисло=новый ОписаниеТипов("Число",,,новый КвалификаторыЧисла(19,0));
   разложение=новый ТаблицаЗначений;
   разложение.Колонки.Добавить("Множитель",тЧисло);
   разложение.Колонки.Добавить("Степень",тЧисло);
   
   если ПростыеЧисла.Найти(вхЧисло)<>Неопределено тогда
          нСтр=разложение.Добавить();
         нСтр.Множитель=вхЧисло;
         нСтр.Степень=1;
         возврат  разложение;
    конецесли;
   
   Граница=(вхЧисло-вхЧисло%2)/2;
   для каждого число из ПростыеЧисла цикл
      если число > Граница тогда
         прервать;
      конецесли;      
      если вхЧисло%число=0 тогда
         нСтр=разложение.Добавить();
         нСтр.Множитель=число;
         нСтр.Степень=1;
         н=число*число;
         пока  вхЧисло%н=0 цикл
            нСтр=разложение.Добавить();
            нСтр.Множитель=число;
             нСтр.Степень=1;
            н=н*число;
         конеццикла;    
      конецесли;      
   конеццикла;   
   
   разложение.Свернуть("Множитель","Степень");
   
   возврат разложение;
КонецФункции   
 Функция zGenerateVar формирует массив комплексных чисел [(Z**i)*(Zсопряженное**(p-i))Предназначение функции РазложитьНаПростыеМножители понятно из ее названия. Аргументами функции является разлагаемое число и массив простых чисел, функция возвращает таблицу значений с колонками Множитель и Степень. Теперь проговорим необходимую последовательность действий. 
Шаг 1. Подготовить таблицу простых чисел с коэффициентами разложения простого числа на сумму квадратов.
Шаг 2 Получим таблицу разложения исследуемого числа на множители.
Шаг 3. Сформируем массив, каждый элемент, которого - это тоже массив, содержащий варианты представления степени простого числа вида Z=4*k+1. Данное разложение нам возвращает функция zGenerateVar.
Шаг 4. С помощью рекуррентной функции получим все варианты представления числа как сумму двух квадратов.
Отметим, что представление числа в виде суммы квадратов возможно только тогда, когда в его разложении присутствуют простые числа вида 4*k+1, а простые числа вида 4*k+3 имеют четную степень, то есть входят в разложение, как полный квадрат. Никаких ограничений на наличие и степень двойки в каноническом представлении числа нет. Приведем фрагмент кода, который реализует второй и третий шаг нашего алгоритма.
      Decompose=РазложитьНаПростыеМножители(i,PrimeNumber);
      arr.Clear();
      Q=1; test=0;
      for each row in Decompose do
         n=row.Множитель;
         p=row.Степень;
         if n=2 then
            z=zNumber(1,1);
            vc=new array;
            vc.Add(zPower(z,p));
            arr.Add(vc);
         else
            find=vt.Find(n,"N");
            if find.a=0 then 
            if p%2=1 then  
                test=0; 
                break;  
             endif;
             Q=Q*n;
             for j=2 to p do
                  Q=Q*n;
             enddo;   
            else
               test=test+1;
               z=zNumber(find.a,find.b);
               arr.Add(zGenerateVar(z,p));
            endif;   
         endif;   
      enddo;
 Исследуемое число хранится в переменной i. В первой строке кода мы получаем разложение на простые множители. Затем в цикле обрабатываем таблицу с найденным разложением. Если после завершения цикла переменная test равна нулю, то данное число нельзя представить как сумму квадратов. Переменная Q хранит произведение степеней простых чисел 4*k+3. Массив arr содержит варианты разложения для остальных множителей канонического представления.
Теперь приведем код рекуррентной функции для получения вариантов разложения числа на сумму квадратов.
Function zSquare(arr,level,mult,Q)
   if level = arr.Count() then
      z=mult[0];
      imax=arr.Count()-1;
      for i=1 to imax do
         z=zMult(z,mult[i]);
      enddo;
      z0=z[0]*z[0];
      z1=z[1]*z[1];
      if z0*z1>0 then
        row=GaussPairs.Add();
        if z0>z1 then   
         row.a=Q*z0;
         row.b=Q*z1;
         else
         row.a=Q*z1;
         row.b=Q*z0;
          endif;
       endif; 
      return true;
   endif;   
   for each z in  arr[level] do
     mult[level]=z;    
     zSquare(arr,level+1,mult,Q);
   enddo;  
EndFunction   
Аргументы функции это: 
  • массив с вариантами arr;
  • переменная level говорит о том с каким элементом данного массива мы работаем на текущем шаге;
  • mult - массив в нем мы собираем все множители разложения;
  • назначение переменной Q мы объяснили в предыдущем абзаце. 
 Найденные разложения хранятся в таблице GaussPairs. Как можно использовать изложенную технику. Рассмотрим решение задачи, вариант которой можно найти в проекте Эйлер. Условия нашей задачи следующие:

Найдите  целые числа x > y > z > 0 такие, что x + y, x - y, x + z, x -z, y + z, y-z все являются квадратами целых чисел.

Введем обозначения: 
Введенные обозначения

Запишем следующие тождества:
x+y=(x+z)+(y-z)
x+y=(x-z)+(y+z)
отсюда получаем
Сумма квадратов
Соотношение (x+y)+(z-y)=(x+z) можно переписать в виде 

Еще один квадрат
Теперь идея решения понятна. Ищем такие числа, квадрат которых имеет несколько представлений в виде суммы квадратов. Условию задачи будут удовлетворять те из них, для которых выполняется условие, что d^2-f^2 есть полный квадрат. Здесь можно скачать обработку, в которой реализован данный алгоритм. Обработка написана для управляемого приложения.




См. также

Подписаться Добавить вознаграждение
Комментарии
1. Asmody (Asmody) 25.12.14 17:46
Я бы числа в структуре хранил.
Function zNumber(Re,Im) Export
   return new Structure("r,i",Re,Im);
EndFunction  

Function zMult(a,b) Export
   retrun new Structure("r,i",
        a.r*b.r - a.i*b.i,
        a.r*b.i + a.i*b.r
   );
EndFunction   
...Показать Скрыть


воспринимается нагляднее
2. Денис Соломасов (Denis S) 29.01.15 22:43
Можете привести пример использования комплексных чисел в типовой конфе? Решали ли Вы этим примером задачу из жизни?
3. Валерий (scientes) 30.01.15 09:40
(2) Denis S, Хороший вопрос, впрочем я предугадал его появление и начал свою заметку фразой "Трудно предположить, что когда-нибудь в бухгалтерском учете понадобятся действия с мнимой единицей." Разумеется, в типовой конфигурации комплексные числа не присутствуют и вряд ли появятся. Изложенный пример, показывает как можно на встроенном языке решать задачи, которые абсолютно далеки от изначальной области применения платформы 1С:Предприятие.
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа