#import "../title_page_template.typ": title_page
#import "../layouts.typ": *
#set text(font: "New Computer Modern", size: 14pt)
#set page(margin: (top: 2cm, bottom: 2cm, left: 2cm, right: 2cm))
#set heading(numbering: "1.")

#show figure.where(kind: table): set figure.caption(position: top, separator: [ -- ])

#title_page(1, [Оценка вычислительной сложности алгоритма])

#un_heading([Оглавление])

#outline(
  title: none
)

#pagebreak()

#set page(numbering: "1")

#head1([= Условие задачи])

#par(
  justify: true, 
  [*Задание: *разработать алгоритм задачи варианта. Определить функцию, показывающую зависимость количества выполняемых инструкций от размера задачи, функцию емкостной сложности алгоритма.]
)

#par(
  justify: true, 
  [*Требования:* \
  #enum([Выполнить разработку алгоритма задачи варианта, представляя последовательность как массив из n значений. Записать алгоритм на псевдокоде.],
  [Определить для полученного алгоритма, функциональную зависимость (функцию), указывающую зависимость количества выполняемых инструкций от размера задачи.],
  [Технологию подсчета количества инструкций алгоритма представить в виде таблицы.
  ],
  [Определить функцию (функции: наилучший, наихудший и средний случаи) зависимости количества инструкций алгоритма от размера задачи и от данных. Для этого выполнить суммарный подсчет всех значений столбца Количество выполнений инструкции, учитывая влияние данных на количество выполняемых инструкций.],
  [Реализовать алгоритм.],
  [Разработать тесты для доказательства корректной работы алгоритма. Подготовку тестов выполнить в таблице.],
  [Выполнить отладку и тестирование алгоритма. 
  Определить емкостную сложность алгоритма.] )

  ]
)

#par(
  justify: true,
  [
    *Вариант 22.* Дано натуральное число n и последовательность натуральных чисел. Определить количество чисел последовательности, являющихся палиндромами.
  ]
)

#pagebreak()

#head1([= Разработка решения])

#head2([== Таблица с количеством выполняемых инструкций, заполненная согласно требованиям задания])

#par(
  justify: true,
  [#indent Пусть $rho(n) = log_10 n + 1$ -- функция, вычисляющая количество выполнений некоторой инструкции.]
)

#tab_caption(1, [Форма представления алгоритма при получении функции зависимости количества выполняемых инструкций от размера задачи])

#figure(
  kind: table,

  table(
    columns: 3,
    align: (center, left, center),
    table.header(
      [Номер строки инструкции алгоритма], table.cell(
        align: center,
        [Инструкция (оператор) алгоритма]
      ), [Количество выполнений инструкции]
    ),
    [1], [quantity $<-$ 0], [1],
    [2], [if array$[i]$ = 0 then], [2],
    [3], [#tab continue], [1],
    [4], [endIf], [],
    [5], [pow $<-$ 1], [1],
    [6], [while array$[i]$ $mod$ pow $eq.not$ array$[i]$ do], [$4 times rho("array[i]")$],
    [7], [#tab pow $<-$ pow $times$ 10], [*:(*],
    [8], [od], [], 
    [9], [reversed $<-$ 0], [1],
    [10], [temp $<-$ array[i]], [1],
    [11], [while pow $>$ 1 do], [1],
    [12], [#tab digit $<-$ temp $mod$ 10], [*:(* 2], 
    [13], [#tab reversed $<-$ reversed $times$ 10 + digit], [*:(* 3], 
    [14], [#tab temp $<-$ temp $"div"$ 10], [*:(* 2],
    [15], [#tab pow $<-$ pow $"div"$ 10], [*:(* 2],
    [16], [od], [],
    [17], [if array$[i]$ = reversed then], [1],
    [18], [#tab quantity $<-$ quantity + 1], [2],
    [19], [endIf], [],
    [20], [return quantity], [1]
  )
)

#pagebreak()

#head2([== Функциональные зависимости, полученные в результате анализа алгоритма])

#par(
  justify: true,
  [#indent _Здесь просто переписаны результаты для неэффективного алгоритма, так что нахождение истинных функциональных зависимосей оставляется в качестве самостоятельного упражнения для заинтересованных читателей #emoji.face.grin _.]
)

#par(
  justify: true,
  [#enum([Заметим, что в лучшем случае все числа будут отрицательными, а значит не будут являться палиндромами. В таком случае выполняется $F_"лучш"=3×n+2$ инструкций.],
	[В худшем случае все числа не будут являться палиндромами, а их длина будет наибольшей. Для типа int в языке С++ максимальная длина составляет 10 символов (для чисел, не меньших $2×10^9$). В таком случае будет выполняться $F_"худш"=2+n(8+11×l_i)=118×n+2$ инструкций.])
])

#pagebreak()

#head2([== Код алгоритма на языке C++])

#let code = read("../../src/work_1/main.cpp")
#raw(code, lang: "cpp")

#pagebreak()

#head2([== Разработанные тесты])

#tab_caption(2, [Таблица тестов])

#figure(
  kind: table,

  table(
    columns: 3,
    align: center,
    table.header(
      [Номер теста], [Входные данные], [Эталон результата (ожидаемый результат)]
    ),
    [1], [$n = 1$ \ $"arr" = {3}$], [1],
    [2], [$n = 3$ \ $"arr" = {-1, -2, -3}$], [0],
    [3], [$n = 6$ \ $"arr" = {121, 16, 85, 13, 22, 5}$], [3],
    [4], [$ n = 20 $  $"arr" = {376, 451, 438, 146, \ 717, 565, 216, 498, \ 391, 111, 213, 617, \ 204, 495, 484, 604, \ 540, 411, 46, 651}$], [4],
  )
)

#pagebreak()

#head2([== Скриншоты результатов тестирования])

#set figure.caption(separator: [ -- ])

#figure(
  kind: image,
  supplement: [Рисунок],
  
  image("images/test1.png", width: 60%),
  caption: [Тест 1]
)

#figure(
  kind: image,
  supplement: [Рисунок],
  
  image("images/test2.png", width: 60%),
  caption: [Тест 2]
)

#figure(
  kind: image,
  supplement: [Рисунок],
  
  image("images/test3.png", width: 60%),
  caption: [Тест 3]
)

#figure(
  kind: image,
  supplement: [Рисунок],
  
  image("images/test4.png", width: 75%),
  caption: [Тест 4]
)

#pagebreak()

#head2([== Результаты исследования алгоритма на различных объемах данных и получение времени его выполнения])

#tab_caption(3, [Параметры алгоритма при оценке сложности алгоритма])

#figure(
  table(
    columns: 4,
    align: center,
    table.header(
      [Размер задачи (n)], [Время выполнения алгоритма (сек)], [Количество инструкций по формуле функции (T)], [Время выполнения T инструкций на компьютере (T / быстродействие процессора) (сек)]
    ),
    [1], [$< 10^(-9)$], [120], [0,00000003],
    [2], [$0,000061$], [11802], [0,000003],
    [3], [$0,000553$], [118020], [0,00003],
    [4], [$0,002$], [590002], [0,00016],
  )
)

#pagebreak()

#head2([== Анализ выполнения алгоритма])

#par(
  [#indent Анализируя данные из таблицы 3, можно прийти к выводу, что время выполнения алгоритма линейно растет при увеличении размера задачи.]
)