Обсуждение участника:VolkovNikita94: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показано 11 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
== Статья [[Участник:VolkovNikita94/Алгоритм Ланцоша для точной арифметики (без переортогонализации)]] ==
+
<tabs>
  
−
=== Замечания по тексту ===
+
<tab name="Специальный_пример_1_n4">
−
* В разделе 1.5 помимо текста программы нужно дать словесные пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:09, 27 октября 2016 (MSK)
+
{{#widget:Algoviewer
−
* Подписи к рисунку в разделе 2.4 очень мелкие, почти неразличимые. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:06, 16 ноября 2016 (MSK)
+
|url=XML_task_001/Example_001.html
−
* В разделе 2.4 не приведены все параметры запуска теста - какой компилятор, с какими опциями использовался, какая версия MKL, на каких узлах проводился запуск и т.д. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:06, 16 ноября 2016 (MSK)  
+
|width=1200
−
** Это замечание остаётся. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:56, 21 ноября 2016 (MSK)  
+
|height=800
−
* В разделе 2.4 не приведена использованная в экспериментах реализация алгоритма. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:06, 16 ноября 2016 (MSK)
+
|border=1
−
* Рисунки в статье не пронумерованы. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:56, 21 ноября 2016 (MSK)
+
}}
−
* На рис. в разделе 2.4 по-прежнему очень мелкие подписи. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:56, 21 ноября 2016 (MSK)  
+
<br>
 +
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
 +
C++ реализация:
 +
<div class="mw-collapsible-content">
 +
<source lang = "c++">
 +
for (int i = 1; i <= n; ++i) {
 +
C[i] = C[i - 2];
 +
}
 +
for (int i = 1; i <= n; ++i) {
 +
for (int j = 1; j <= n; ++j) {
 +
B[i][j] = B[i][j] + C[i];
 +
}
 +
}
 +
for (int i = 1; i <= n; ++i) {
 +
for (int j = 1; j <= n; ++j) {
 +
for (int k = 1; k <= n; ++k) {
 +
A[i][j][k] = A[i][j][k] + A[i - 1][j][1];
 +
}
 +
}
 +
}
 +
</source>
 +
</div>
 +
</div>
 +
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
 +
Новая разметка:
 +
<div class="mw-collapsible-content">
 +
<source lang = "xml">
 +
<algo>
 +
  <params>
 +
<param name = "N" type = "int"></param>
 +
  </params>
 +
  <block id = "0" dims = "1">
 +
<arg name = "i" val = "1..N"></arg>
 +
<vertex condition = "" type = "0">
 +
<in src = “i – 2”></in>
 +
</vertex>
 +
  </block>
 +
  <block id = "1" dims = "2">
 +
<arg name = "i" val = "1..N"></arg>
 +
<arg name = "j" val = "1..N"></arg>
 +
<vertex condition = "" type = "0">
 +
                <in bsrc = "0" src = "i"></in>
 +
</vertex>
 +
  </block>
 +
  <block id = "2" dims = "3">
 +
<arg name = "i" val = "1..N"></arg>
 +
<arg name = "j" val = "1..N"></arg>
 +
        <arg name = "k" val = "1..N"></arg>
 +
<vertex condition = "(k == 1) || (i == 1)" type = "0">
 +
</vertex>
 +
<vertex condition = "(k > 1) && (i > 1)" type = "0">
 +
<in src = “1, j, 1”></in>
 +
</vertex>
 +
  </block>
 +
</algo>
 +
</source>
 +
</div>
 +
</div>
 +
</tab>
  
 +
<tab name="Специальный_пример_1_n8">
 +
{{#widget:Algoviewer
 +
|url=XML_task_001_n8/Example_001.html
 +
|width=1200
 +
|height=800
 +
|border=1
 +
}}
 +
<br>
 +
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
 +
C++ реализация:
 +
<div class="mw-collapsible-content">
 +
<source lang = "c++">
 +
for (int i = 1; i <= n; ++i) {
 +
C[i] = C[i - 2];
 +
}
 +
for (int i = 1; i <= n; ++i) {
 +
for (int j = 1; j <= n; ++j) {
 +
B[i][j] = B[i][j] + C[i];
 +
}
 +
}
 +
for (int i = 1; i <= n; ++i) {
 +
for (int j = 1; j <= n; ++j) {
 +
for (int k = 1; k <= n; ++k) {
 +
A[i][j][k] = A[i][j][k] + A[i - 1][j][1];
 +
}
 +
}
 +
}
 +
</source>
 +
</div>
 +
</div>
 +
</tab>
  
 +
<tab name="Специальный_пример_2_n4">
 +
{{#widget:Algoviewer
 +
|url=XML_task_002/Example_001.html
 +
|width=1200
 +
|height=800
 +
|border=1
 +
}}
 +
<br>
 +
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
 +
C++ реализация:
 +
<div class="mw-collapsible-content">
 +
<source lang = "c++">
 +
for (int i = 1; i <= n; ++i) {
 +
C[i] = C[i] * e;
 +
}
 +
for (int i = 1; i <= n; ++i) {
 +
for (int j = 1; j <= n; ++j) {
 +
B[i][j] = B[i - 1][j - 1];
 +
}
 +
}
 +
for (int i = 1; i <= n; ++i) {
 +
for (int j = 1; j <= n; ++j) {
 +
for (int k = 1; k <= n; ++k) {
 +
A[i][j][k] = A[i][j][k] + A[i][j - 1][k - 2];
 +
}
 +
A[i][j][n] = A[i][j][n] + B[i][j];
 +
}
 +
}
 +
</source>
 +
</div>
 +
</div>
 +
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
 +
Новая разметка:
 +
<div class="mw-collapsible-content">
 +
<source lang = "xml">
 +
<algo>
 +
<params>
 +
<param name = "N" type = "int"></param>
 +
</params>
 +
<block id = "0" dims = "1">
 +
<arg name = "I" val = "1..N"></arg>
 +
<vertex condition = "" type = "1">
 +
</vertex>
 +
  </block>
 +
<block id = "0" dims = "2">
 +
<arg name = "I" val = "1..N"></arg>
 +
<arg name = "J" val = "1..N"></arg>
 +
<vertex condition = "" type = "1">
 +
<in src = "I - 1, J - 1"></in>
 +
</vertex>
 +
</block>
 +
<block id = "2" dims = "3">
 +
<arg name = "I" val = "1..N"></arg>
 +
<arg name = "J" val = "1..N"></arg>
 +
<arg name = "K" val = "1..N"></arg>
 +
<vertex condition = "K == 1" type = "2">
 +
<in bsrc = "1" src = "I, J"></in>
 +
<in src = "I - 1, J, K + 2"></in>
 +
</vertex>
 +
<vertex condition = "K > 1" type = "1">
 +
<in src = "I - 1, J, K + 2"></in>
 +
</vertex>
 +
</block>
 +
</algo>
 +
</source>
 +
</div>
 +
</div>
 +
</tab>
  
−
== Исправления. ==
+
<tab name="Специальный_пример_2_n8">
 +
{{#widget:Algoviewer
 +
|url=XML_task_002_n8/Example_001.html
 +
|width=1200
 +
|height=800
 +
|border=1
 +
}}
 +
<br>
 +
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
 +
C++ реализация:
 +
<div class="mw-collapsible-content">
 +
<source lang = "c++">
 +
for (int i = 1; i <= n; ++i) {
 +
C[i] = C[i] * e;
 +
}
 +
for (int i = 1; i <= n; ++i) {
 +
for (int j = 1; j <= n; ++j) {
 +
B[i][j] = B[i - 1][j - 1];
 +
}
 +
}
 +
for (int i = 1; i <= n; ++i) {
 +
for (int j = 1; j <= n; ++j) {
 +
for (int k = 1; k <= n; ++k) {
 +
A[i][j][k] = A[i][j][k] + A[i][j - 1][k - 2];
 +
}
 +
A[i][j][n] = A[i][j][n] + B[i][j];
 +
}
 +
}
 +
</source>
 +
</div>
 +
</div>
 +
</tab>
  
−
Поправили замечания, прогнали на большом числе процессоров.
+
<tab name="Преобразование_фурье">
 +
{{#widget:Algoviewer
 +
|url=XML_Fourier/Example_001.html
 +
|width=1200
 +
|height=800
 +
|border=1
 +
}}
 +
<br>
 +
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
 +
Новая разметка:
 +
<div class="mw-collapsible-content">
 +
<source lang = "xml">
 +
<algo>
 +
<params>
 +
<param name = "N" type = "int" value = "3"></param>
 +
</params>
 +
<block id = "0" dims = "2">
 +
<arg name = "I" val = "1..N"></arg>
 +
<arg name = "J" val = "1..2^N"></arg>
 +
<vertex condition = "(J - 1) % (2^I) < 2^(I - 1)" type = "1">
 +
<in src = "I - 1, J"></in>
 +
<in src = "I - 1, J + 2^(I -1)"></in>
 +
</vertex>
 +
<vertex condition = "(J - 1) % (2^I) >= 2^(I - 1)" type = "2">
 +
<in src = "I - 1, J"></in>
 +
<in src = "I - 1, J - 2^(I - 1)"></in>
 +
</vertex>
 +
</block>
 +
</algo>
 +
</source>
 +
</div>
 +
</div>
 +
</tab>
  
−
Мой личный комментарий "вне задания": есть довольно любопытная вещь, на которую стоит обратить внимание - небольшие скачки производительности, которые заметны на небольшом числе процессов для небольшого размера задачи. Для большего числа процессов эти скачки полностью не охватываются ( см. линию для 50 процессоров ), но, вероятно, имеют место быть. Какая-никакая, а "характерная особенность", спасибо кэшам ? На 100 процессорах какое-то безумие :)
+
</tabs>
  
−
* для стабильности можно просчитать задачу несколько раз во время одного запуска и сравнить времена (потом взять среднее или минимальное), отличия но 10% должны получиться. А если сравнивать времена различных запуском (когда очередь выделит узлы с другими номерами), то отличие в 30% тоже могут случиться. На заре установки Ломоносова знакомые исследовали это и составили карту скоростей обменов между физическими узлами, а потом даже одсуждали это с производителями. Вроде бы даже у них есть публикации... (ИНК) P.S. Если замеренное время счета получается меньше 1 сек., то лучше запустить задачу в цикле несколько раз подряд.
+
== Тестовые варианты 2020 ==
  
−
== Новые замечания ==
+
<tabs>
−
* ваша работа дошла до проверяющего только вчера, так что извиняйте за задержку (ИНК)
 
−
* везде удрать * как символ математического умножения (в самом крайнем случае можно использовать \cdot)
 
−
* в формулах ну очень часто неверно набраны верхние индексы, состоящие более чем из одной буквы. Не забывайте фигурные скобки! (например, стоит набирать K^{-1})
 
−
* п.1.5 греческие буквы в обозначениях лучше сделать греческими, добавив \ (например, \alpha, \beta)
 
−
* п.1.6 поправить показатель степени "в среднем затрачивается <math>O(k^{2.3})</math> операций"
 
−
* п.1.7 "из статей от матрично-векторных операциях" (статьи в Алговики? добавить линк на них)
 
−
* п.1.8 "Ланцоща" --> "Ланцоша", "классисифкации" --> "классификации" (безобразие! вы очень торопились при наборе... --> в режиме правки взять всю статью мышкой и поместить в Word чтобы он подчеркнул ошибочно набранные слова, после чего исправить все описки)
 
−
* п.2.4 "предметом отдельных статей ( QR-алгоритм, метод «Разделяй-и-властвуй», итерации Арнольди и.т.д. )" (линки на статьи)
 
−
* п.2.4 собственная реализация - это хорошо (MPI v.2.2? может стоит упомянуть это? И вообще сказать, что это гибридная MPI+OpenMP реализация. А сейчас модно писать код прямо с *.h файле без *.cpp? Хотя никому не мешает, реализация хорошая...)
 
−
* п.2.4 "Максимальная эффективность - 30.76%" малоинформативная фраза если не сказано на скольки ядрах, на одном или 800? Неплохо было бы для тех же данных привести пару-тройку графиков ускорения, для двух-трех размерностей матрицы.
 
−
* п.2.7 - замечательно, спасибо
 
−
* п.3 стоит занумеровать и сделать настоящие ссылки
 
  
−
Основные замечания поправил, Леонид скоро зальёт графики ускорения и еще подправит 2.4
+
<tab name="Вариант_01">
 +
{{#widget:Algoviewer
 +
|url=Variant_01/Variant_01.html
 +
|width=1200
 +
|height=800
 +
|border=1
 +
}}
 +
<br>
 +
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
 +
Новая разметка:
 +
<div class="mw-collapsible-content">
 +
<source lang = "xml">
 +
<algo>
 +
<params>
 +
<param name = "N" type = "int"></param>
 +
<param name = "M" type = "int"></param>
 +
  </params>
 +
  <block id = "0" dims = "1">
 +
<arg name = "i" val = "1..N"></arg>
 +
<vertex condition = "" type = "1">
 +
<in src = "i - 2"></in>
 +
</vertex>
 +
  </block>
 +
  <block id = "1" dims = "2">
 +
<arg name = "i" val = "1..N"></arg>
 +
<arg name = "j" val = "1..M"></arg>
 +
<vertex condition = "" type = "1">
 +
<in src = "i - 1, j - 1"></in>
 +
<in bsrc = "0" src = "i"></in>
 +
</vertex>
 +
  </block>
 +
  <block id = "2" dims = "3">
 +
<arg name = "i" val = "1..N"></arg>
 +
<arg name = "j" val = "1..M"></arg>
 +
<arg name = "k" val = "1..N-1"></arg>
 +
<vertex condition = "(j == 1) and (k == 1)" type = "1">
 +
<in bsrc = "1" src = "i, M"></in>
 +
</vertex>
 +
<vertex condition = "(j > 1) or (k > 1)" type = "1">
 +
<in src = "i - 1, j, 1"></in>
 +
</vertex>
 +
  </block>
 +
</algo>
 +
</source>
 +
</div>
 +
</div>
 +
</tab>
  
−
PS: "модно..." - нет, не модно :) Просто а) программа маленькая и это не мешает, так что нет "против" и б) программа писалась в Visual Studio, где процедура компиляции настроена с отличиями от того, что происходит на кластере; в таком виде при переносе переписывать не нужно вообще ничего, так что есть "за".
+
<tab name="Вариант_02">
 +
{{#widget:Algoviewer
 +
|url=Variant_02/Variant_02.html
 +
|width=1200
 +
|height=800
 +
|border=1
 +
}}
 +
<br>
 +
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
 +
Новая разметка:
 +
<div class="mw-collapsible-content">
 +
<source lang = "xml">
 +
<algo>
 +
<params>
 +
<param name = "N" type = "int"></param>
 +
<param name = "M" type = "int"></param>
 +
  </params>
 +
  <block id = "0" dims = "1">
 +
<arg name = "i" val = "1..N"></arg>
 +
<vertex condition = "" type = "1">
 +
<in src = "i - 1"></in>
 +
</vertex>
 +
  </block>
 +
  <block id = "1" dims = "2">
 +
<arg name = "i" val = "1..N"></arg>
 +
<arg name = "j" val = "1..M"></arg>
 +
<vertex condition = "" type = "1">
 +
<in src = "i - 2, j"></in>
 +
</vertex>
 +
  </block>
 +
  <block id = "2" dims = "3">
 +
<arg name = "i" val = "1..N"></arg>
 +
<arg name = "j" val = "1..M"></arg>
 +
<arg name = "k" val = "1..N-1"></arg>
 +
<vertex condition = "(j == 1) and (k == 1)" type = "1">
 +
<in bsrc = "0" src = "i"></in>
 +
<in bsrc = "1" src = "i, M"></in>
 +
</vertex>
 +
<vertex condition = "(j > 1) or (k > 1)" type = "1">
 +
<in src = "i, j - 1, 1"></in>
 +
</vertex>
 +
  </block>
 +
</algo>
 +
</source>
 +
</div>
 +
</div>
 +
</tab>
  
−
-Сделано. Добавил графики ускорения и пояснения к 2.4
+
<tab name="Вариант_03">
 +
{{#widget:Algoviewer
 +
|url=Variant_03/Variant_03.html
 +
|width=1200
 +
|height=800
 +
|border=1
 +
}}
 +
<br>
 +
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
 +
Новая разметка:
 +
<div class="mw-collapsible-content">
 +
<source lang = "xml">
 +
<algo>
 +
<params>
 +
<param name = "N" type = "int"></param>
 +
<param name = "M" type = "int"></param>
 +
  </params>
 +
  <block id = "0" dims = "1">
 +
<arg name = "i" val = "1..N"></arg>
 +
<vertex condition = "" type = "1">
 +
</vertex>
 +
  </block>
 +
  <block id = "1" dims = "2">
 +
<arg name = "i" val = "1..N"></arg>
 +
<arg name = "j" val = "1..M"></arg>
 +
<vertex condition = "" type = "1">
 +
<in src = "i, j - 2"></in>
 +
<in bsrc = "0" src = "i"></in>
 +
</vertex>
 +
  </block>
 +
  <block id = "2" dims = "3">
 +
<arg name = "i" val = "1..N"></arg>
 +
<arg name = "j" val = "1..M"></arg>
 +
<arg name = "k" val = "1..N-1"></arg>
 +
<vertex condition = "(j == 1) and (k == 1)" type = "1">
 +
<in bsrc = "1" src = "i, M"></in>
 +
</vertex>
 +
<vertex condition = "(j > 1) or (k > 1)" type = "1">
 +
<in src = "i, j - 1, k"></in>
 +
</vertex>
 +
  </block>
 +
</algo>
  
−
== Последние замечания ==
+
</source>
−
* Очень хорошо! При стремлении к соверщенству осталось сделать самую малость:
+
</div>
−
* в оставшихся местах (в том числе во врезке) убрать звездочку * в качестве символа умножения
+
</div>
−
* в п.2.4 конечно сбивает на осях количество узлов вместо количества нитей, непривычно прикидывать эффективность расчетов, но давайте оставим как есть, а для ясности напишем что-то вроде: для 50 проц. наблюдается эффективность более 50%
+
</tab>
−
* в п.2.4 давайте три новых рисунка 4,5,6 объединим в один, тогда будет виднее повышение эффективности с ростом размера задачи, а графики пусть будут даны разным цветов
 
−
* P.S. ввиду приближения зачетной сессии я проставляю пометку принятости работы, но буду признателен если вы таки доделаете оставшиеся простые правки... (ИНК)
 
  
−
Спасибо от меня и от Никиты !
+
<tab name="Вариант_04">
 +
{{#widget:Algoviewer
 +
|url=Variant_04/Variant_04.html
 +
|width=1200
 +
|height=800
 +
|border=1
 +
}}
 +
<br>
 +
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
 +
Новая разметка:
 +
<div class="mw-collapsible-content">
 +
<source lang = "xml">
 +
<algo>
 +
<params>
 +
<param name = "N" type = "int"></param>
 +
<param name = "M" type = "int"></param>
 +
  </params>
 +
  <block id = "0" dims = "1">
 +
<arg name = "i" val = "1..N"></arg>
 +
<vertex condition = "" type = "1">
 +
<in src = "i - 1"></in>
 +
</vertex>
 +
  </block>
 +
  <block id = "1" dims = "2">
 +
<arg name = "i" val = "1..N"></arg>
 +
<arg name = "j" val = "1..M"></arg>
 +
<vertex condition = "" type = "1">
 +
<in src = "i - 1, j - 1"></in>
 +
<in bsrc = "0" src = "i"></in>
 +
</vertex>
 +
  </block>
 +
  <block id = "2" dims = "3">
 +
<arg name = "i" val = "1..N"></arg>
 +
<arg name = "j" val = "1..M"></arg>
 +
<arg name = "k" val = "1..N-1"></arg>
 +
<vertex condition = "(j == 1) and (k == 1)" type = "1">
 +
<in bsrc = "1" src = "i, M"></in>
 +
</vertex>
 +
<vertex condition = "(j > 1) or (k > 1)" type = "1">
 +
<in src = "i - 1, j, k"></in>
 +
</vertex>
 +
  </block>
 +
</algo>
 +
</source>
 +
</div>
 +
</div>
 +
</tab>
  
−
- Поправил.
+
</tabs>
−
- Добавил в подпись к графику.
+
 
−
- Добавил 4-ый график со сравнительным анализом.
+
== Параметрика Пакуля ==
 +
 
 +
<tabs>
 +
 
 +
<tab name="Параметрика">
 +
{{#widget:Algoviewer
 +
|url=Variant_parametric/Variant_par.html
 +
|width=1200
 +
|height=800
 +
|border=1
 +
}}
 +
<br>
 +
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
 +
Новая разметка:
 +
<div class="mw-collapsible-content">
 +
<source lang = "xml">
 +
<algo>
 +
<params>
 +
<param name = "N" type = "int"></param>
 +
<param name = "M" type = "int"></param>
 +
<aparam name = "p0" type = "int"></aparam>
 +
<aparam name = "p1" type = "int"></aparam>
 +
<aparam name = "p2" type = "int"></aparam>
 +
<aparam name = "p3" type = "int"></aparam>
 +
<aparam name = "p4" type = "int"></aparam>
 +
<aparam name = "p5" type = "int"></aparam>
 +
</params>
 +
<block id = "0" dims = "1">
 +
<arg name = "i" val = "1..N"></arg>
 +
<vertex condition = "" type = "1">
 +
<in src = "i + p0"></in>
 +
</vertex>
 +
</block>
 +
<block id = "1" dims = "2">
 +
<arg name = "i" val = "1..N"></arg>
 +
<arg name = "j" val = "1..M"></arg>
 +
<vertex condition = "p3 == 0" type = "1">
 +
<in src = "i + p1, j + p2"></in>
 +
</vertex>
 +
<vertex condition = "p3 == 1" type = "1">
 +
<in src = "i + p1, j + p2"></in>
 +
<in bsrc = "0" src = "i"></in>
 +
</vertex>
 +
</block>
 +
<block id = "2" dims = "3">
 +
<arg name = "i" val = "1..N"></arg>
 +
<arg name = "j" val = "1..M"></arg>
 +
<arg name = "k" val = "1..N-1"></arg>
 +
<vertex condition = "(j == 1) and (k == 1) and (p3 == 1)" type = "1">
 +
<in bsrc = "1" src = "i, M"></in>
 +
</vertex>
 +
<vertex condition = "(j == 1) and (k == 1) and (p3 == 0)" type = "1">
 +
<in bsrc = "1" src = "i, M"></in>
 +
<in bsrc = "0" src = "i"></in>
 +
</vertex>
 +
<vertex condition = "((j > 1) or (k > 1)) and (p4 == 1)" type = "1">
 +
<in src = "i - 1 * (1 - p5), j - 1 * p5, 1"></in>
 +
</vertex>
 +
<vertex condition = "((j > 1) or (k > 1)) and (p4 == 0)" type = "1">
 +
<in src = "i - 1 * (1 - p5), j - 1 * p5, k"></in>
 +
</vertex>
 +
</block>
 +
</algo>
 +
</source>
 +
</div>
 +
</div>
 +
</tab>
 +
 
 +
<tab name="Пакулев">
 +
{{#widget:Algoviewer
 +
|url=Variant_pakulev/Variant_pak.html
 +
|width=1200
 +
|height=800
 +
|border=1
 +
}}
 +
<br>
 +
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
 +
Новая разметка:
 +
<div class="mw-collapsible-content">
 +
<source lang = "xml">
 +
<algo>
 +
<params>
 +
<param name = "N" type = "int"></param>
 +
</params>
 +
<block id = "0" dims = "2">
 +
<arg name = "i" val = "1..N"></arg>
 +
<arg name = "j" val = "1..N"></arg>
 +
<vertex condition = "(2 * i + j) <= (N + 1)" type = "1">
 +
</vertex>
 +
<vertex condition = "((2 * i + j) > (N + 1)) and ((i + j) <= N)" type = "1">
 +
<in src = "i - 1, j + 2 * (N + 1 - i - j)"></in>
 +
</vertex>
 +
<vertex condition = "((i + j) > N) and ((2 * i + j) <= (2 * N))" type = "1">
 +
<in src = "i, j - 1 - 2 * ((i + j) - N - 1)"></in>
 +
</vertex>
 +
<vertex condition = "((2 * i + j) > (2 * N)) and ((i + j) <= (2 * N - 1))" type = "1">
 +
<in src = "i - 1 * (2 * i + j - 2 * N), 1"></in>
 +
</vertex>
 +
<vertex condition = "((i + j) > (2 * N - 1))" type = "1">
 +
</vertex>
 +
</block>
 +
</algo>
 +
</source>
 +
</div>
 +
</div>
 +
</tab>
 +
 
 +
</tabs>

Текущая версия на 21:50, 10 августа 2020


C++ реализация: 

for (int i = 1; i <= n; ++i) {
	C[i] = C[i - 2];
}
for (int i = 1; i <= n; ++i) {
	for (int j = 1; j <= n; ++j) {
		B[i][j] = B[i][j] + C[i];
	}
}
for (int i = 1; i <= n; ++i) {
	for (int j = 1; j <= n; ++j) {
		for (int k = 1; k <= n; ++k) {
			A[i][j][k] = A[i][j][k] + A[i - 1][j][1];
		}
	}
}

Новая разметка: 

<algo>
   <params>
	<param name = "N" type = "int"></param>
   </params>
   <block id = "0" dims = "1">
	<arg name = "i" val = "1..N"></arg>
	<vertex condition = "" type = "0">
		<in src = “i – 2”></in>
	</vertex>
   </block>
   <block id = "1" dims = "2">
	<arg name = "i" val = "1..N"></arg>
	<arg name = "j" val = "1..N"></arg>
	<vertex condition = "" type = "0">
                <in bsrc = "0" src = "i"></in>
	</vertex>
   </block>
   <block id = "2" dims = "3">
	<arg name = "i" val = "1..N"></arg>
	<arg name = "j" val = "1..N"></arg>
        <arg name = "k" val = "1..N"></arg>
	<vertex condition = "(k == 1) || (i == 1)" type = "0">
	</vertex>
	<vertex condition = "(k > 1) && (i > 1)" type = "0">
		<in src = “1, j, 1”></in>
	</vertex>
   </block>
</algo>


C++ реализация: 

for (int i = 1; i <= n; ++i) {
	C[i] = C[i - 2];
}
for (int i = 1; i <= n; ++i) {
	for (int j = 1; j <= n; ++j) {
		B[i][j] = B[i][j] + C[i];
	}
}
for (int i = 1; i <= n; ++i) {
	for (int j = 1; j <= n; ++j) {
		for (int k = 1; k <= n; ++k) {
			A[i][j][k] = A[i][j][k] + A[i - 1][j][1];
		}
	}
}


C++ реализация: 

for (int i = 1; i <= n; ++i) {
	C[i] = C[i] * e;
}
for (int i = 1; i <= n; ++i) {
	for (int j = 1; j <= n; ++j) {
		B[i][j] = B[i - 1][j - 1];
	}
}
for (int i = 1; i <= n; ++i) {
	for (int j = 1; j <= n; ++j) {
		for (int k = 1; k <= n; ++k) {
			A[i][j][k] = A[i][j][k] + A[i][j - 1][k - 2];
		}
		A[i][j][n] = A[i][j][n] + B[i][j];
	}
}

Новая разметка: 

<algo>
	<params>
		<param name = "N" type = "int"></param>
	</params>
	<block id = "0" dims = "1">
		<arg name = "I" val = "1..N"></arg>
		<vertex condition = "" type = "1">
		</vertex>
  </block>
	<block id = "0" dims = "2">
		<arg name = "I"	val = "1..N"></arg>
		<arg name = "J" val = "1..N"></arg>
		<vertex condition = "" type = "1">
			<in src = "I - 1, J - 1"></in>
		</vertex>
	</block>
	<block id = "2" dims = "3">
		<arg name = "I" val = "1..N"></arg>
		<arg name = "J" val = "1..N"></arg>
		<arg name = "K" val = "1..N"></arg>
		<vertex condition = "K == 1" type = "2">
			<in bsrc = "1" src = "I, J"></in>
			<in src = "I - 1, J, K + 2"></in>
		</vertex>
		<vertex condition = "K > 1" type = "1">
			<in src = "I - 1, J, K + 2"></in>
		</vertex>
	</block>
</algo>


C++ реализация: 

for (int i = 1; i <= n; ++i) {
	C[i] = C[i] * e;
}
for (int i = 1; i <= n; ++i) {
	for (int j = 1; j <= n; ++j) {
		B[i][j] = B[i - 1][j - 1];
	}
}
for (int i = 1; i <= n; ++i) {
	for (int j = 1; j <= n; ++j) {
		for (int k = 1; k <= n; ++k) {
			A[i][j][k] = A[i][j][k] + A[i][j - 1][k - 2];
		}
		A[i][j][n] = A[i][j][n] + B[i][j];
	}
}


Новая разметка: 

<algo>
	<params>
		<param name = "N" type = "int" value = "3"></param>
	</params>
	<block id = "0" dims = "2">
		<arg name = "I"	val = "1..N"></arg>
		<arg name = "J" val = "1..2^N"></arg>
		<vertex condition = "(J - 1) % (2^I) < 2^(I - 1)" type = "1">
			<in src = "I - 1, J"></in>
			<in src = "I - 1, J + 2^(I -1)"></in>
		</vertex>
		<vertex condition = "(J - 1) % (2^I) >= 2^(I - 1)" type = "2">
			<in src = "I - 1, J"></in>
			<in src = "I - 1, J - 2^(I - 1)"></in>
		</vertex>
	</block>
</algo>

1 Тестовые варианты 2020


Новая разметка: 

<algo>
	<params>
		<param name = "N" type = "int"></param>
		<param name = "M" type = "int"></param>
  </params>
  <block id = "0" dims = "1">
		<arg name = "i" val = "1..N"></arg>
		<vertex condition = "" type = "1">
			<in src = "i - 2"></in>
		</vertex>
  </block>
  <block id = "1" dims = "2">
		<arg name = "i" val = "1..N"></arg>
		<arg name = "j" val = "1..M"></arg>
		<vertex condition = "" type = "1">
			<in src = "i - 1, j - 1"></in>
			<in bsrc = "0" src = "i"></in>
		</vertex>
  </block>
  <block id = "2" dims = "3">
		<arg name = "i" val = "1..N"></arg>
		<arg name = "j" val = "1..M"></arg>
		<arg name = "k" val = "1..N-1"></arg>
		<vertex condition = "(j == 1) and (k == 1)" type = "1">
			<in bsrc = "1" src = "i, M"></in>
		</vertex>
		<vertex condition = "(j > 1) or (k > 1)" type = "1">
			<in src = "i - 1, j, 1"></in>
		</vertex>
  </block>
</algo>


Новая разметка: 

<algo>
	<params>
		<param name = "N" type = "int"></param>
		<param name = "M" type = "int"></param>
  </params>
  <block id = "0" dims = "1">
		<arg name = "i" val = "1..N"></arg>
		<vertex condition = "" type = "1">
			<in src = "i - 1"></in>
		</vertex>
  </block>
  <block id = "1" dims = "2">
		<arg name = "i" val = "1..N"></arg>
		<arg name = "j" val = "1..M"></arg>
		<vertex condition = "" type = "1">
			<in src = "i - 2, j"></in>
		</vertex>
  </block>
  <block id = "2" dims = "3">
		<arg name = "i" val = "1..N"></arg>
		<arg name = "j" val = "1..M"></arg>
		<arg name = "k" val = "1..N-1"></arg>
		<vertex condition = "(j == 1) and (k == 1)" type = "1">
			<in bsrc = "0" src = "i"></in>
			<in bsrc = "1" src = "i, M"></in>
		</vertex>
		<vertex condition = "(j > 1) or (k > 1)" type = "1">
			<in src = "i, j - 1, 1"></in>
		</vertex>
  </block>
</algo>


Новая разметка: 

<algo>
	<params>
		<param name = "N" type = "int"></param>
		<param name = "M" type = "int"></param>
  </params>
  <block id = "0" dims = "1">
		<arg name = "i" val = "1..N"></arg>
		<vertex condition = "" type = "1">
		</vertex>
  </block>
  <block id = "1" dims = "2">
		<arg name = "i" val = "1..N"></arg>
		<arg name = "j" val = "1..M"></arg>
		<vertex condition = "" type = "1">
			<in src = "i, j - 2"></in>
			<in bsrc = "0" src = "i"></in>
		</vertex>
  </block>
  <block id = "2" dims = "3">
		<arg name = "i" val = "1..N"></arg>
		<arg name = "j" val = "1..M"></arg>
		<arg name = "k" val = "1..N-1"></arg>
		<vertex condition = "(j == 1) and (k == 1)" type = "1">
			<in bsrc = "1" src = "i, M"></in>
		</vertex>
		<vertex condition = "(j > 1) or (k > 1)" type = "1">
			<in src = "i, j - 1, k"></in>
		</vertex>
  </block>
</algo>


Новая разметка: 

<algo>
	<params>
		<param name = "N" type = "int"></param>
		<param name = "M" type = "int"></param>
  </params>
  <block id = "0" dims = "1">
		<arg name = "i" val = "1..N"></arg>
		<vertex condition = "" type = "1">
			<in src = "i - 1"></in>
		</vertex>
  </block>
  <block id = "1" dims = "2">
		<arg name = "i" val = "1..N"></arg>
		<arg name = "j" val = "1..M"></arg>
		<vertex condition = "" type = "1">
			<in src = "i - 1, j - 1"></in>
			<in bsrc = "0" src = "i"></in>
		</vertex>
  </block>
  <block id = "2" dims = "3">
		<arg name = "i" val = "1..N"></arg>
		<arg name = "j" val = "1..M"></arg>
		<arg name = "k" val = "1..N-1"></arg>	
		<vertex condition = "(j == 1) and (k == 1)" type = "1">
			<in bsrc = "1" src = "i, M"></in>
		</vertex>
		<vertex condition = "(j > 1) or (k > 1)" type = "1">
			<in src = "i - 1, j, k"></in>
		</vertex>
  </block>
</algo>

2 Параметрика Пакуля


Новая разметка: 

<algo>
	<params>
		<param name = "N" type = "int"></param>
		<param name = "M" type = "int"></param>
		<aparam name = "p0" type = "int"></aparam>
		<aparam name = "p1" type = "int"></aparam>
		<aparam name = "p2" type = "int"></aparam>
		<aparam name = "p3" type = "int"></aparam>
		<aparam name = "p4" type = "int"></aparam>
		<aparam name = "p5" type = "int"></aparam>
	</params>
	<block id = "0" dims = "1">
		<arg name = "i" val = "1..N"></arg>
		<vertex condition = "" type = "1">
			<in src = "i + p0"></in>
		</vertex>
	</block>
	<block id = "1" dims = "2">
		<arg name = "i" val = "1..N"></arg>
		<arg name = "j" val = "1..M"></arg>
		<vertex condition = "p3 == 0" type = "1">
			<in src = "i + p1, j + p2"></in>
		</vertex>
		<vertex condition = "p3 == 1" type = "1">
			<in src = "i + p1, j + p2"></in>
			<in bsrc = "0" src = "i"></in>
		</vertex>
	</block>
	<block id = "2" dims = "3">
		<arg name = "i" val = "1..N"></arg>
		<arg name = "j" val = "1..M"></arg>
		<arg name = "k" val = "1..N-1"></arg>
		<vertex condition = "(j == 1) and (k == 1) and (p3 == 1)" type = "1">
			<in bsrc = "1" src = "i, M"></in>
		</vertex>
		<vertex condition = "(j == 1) and (k == 1) and (p3 == 0)" type = "1">
			<in bsrc = "1" src = "i, M"></in>
			<in bsrc = "0" src = "i"></in>
		</vertex>
		<vertex condition = "((j > 1) or (k > 1)) and (p4 == 1)" type = "1">
			<in src = "i - 1 * (1 - p5), j - 1 * p5, 1"></in>
		</vertex>
		<vertex condition = "((j > 1) or (k > 1)) and (p4 == 0)" type = "1">
			<in src = "i - 1 * (1 - p5), j - 1 * p5, k"></in>
		</vertex>
	</block>
</algo>


Новая разметка: 

<algo>
	<params>
		<param name = "N" type = "int"></param>
	</params>
	<block id = "0" dims = "2">
		<arg name = "i" val = "1..N"></arg>
		<arg name = "j" val = "1..N"></arg>
		<vertex condition = "(2 * i + j) <= (N + 1)" type = "1">
		</vertex>
		<vertex condition = "((2 * i + j) > (N + 1)) and ((i + j) <= N)" type = "1">
			<in src = "i - 1, j + 2 * (N + 1 - i - j)"></in>
		</vertex>
		<vertex condition = "((i + j) > N) and ((2 * i + j) <= (2 * N))" type = "1">
			<in src = "i, j - 1 - 2 * ((i + j) - N - 1)"></in>
		</vertex>
		<vertex condition = "((2 * i + j) > (2 * N)) and ((i + j) <= (2 * N - 1))" type = "1">
			<in src = "i - 1 * (2 * i + j - 2 * N), 1"></in>
		</vertex>
		<vertex condition = "((i + j) > (2 * N - 1))" type = "1">
		</vertex>
	</block>
</algo>
Источник — https://algowiki-project.org/w/ru/index.php?title=Обсуждение_участника:VolkovNikita94&oldid=28373