Сравнил скорость работы "наивного" и "продвинутого" алгоритмов. Также для ускорения работы программы использовал передачу указателей на переменную и массив в функцию.
Условия задачи
"2520 - самое маленькое число, которое делится без остатка на все числа от 1 до 10.
Какое самое маленькое число делится нацело на все числа от 1 до 20?"
Решаю задачу "наивным" способом
В программе использовал библиотеки <stdio.h> и <stdbool.h>, подробнее о библиотеках можно прочитать здесь.
Функция isDiv() работает буквально, как в указано в задании: принимает аргумент, делит его на числа от 2 до 20 включительно (на 1 делятся все числа) и вернет true только, если на все их он делится без остатка (num_arg%i != 0).
Далее в цикле while в функцию передаются натуральные числа до тех пор, пока не будет найдено искомое самое маленькое число.
Все просто-понятно и, как и ожидалось, неэффективно. Решает дольше секунды.
"Продвинутый" вариант программы
В этой программе использовал два способа для ускорения ее работы: применил более быстрый алгоритм и передачу в функцию не самих данных, а указателей на них.
Суть более быстрого алгоритма
Чтобы не проверять каждое число, делится ли оно нацело на числа до 20, можно, например, перемножить все числа от 1 до 20 и получить число, которое заведомо будет делиться на все из них, вот только оно не будет минимальным.
Но обязательно ли умножать на все числа? Так, например:
12 = 3*4 =3*2*2 и таким образом число 12 само делится на 1, 2, 3, 4 и 12 и достаточно использовать лишь его.
Суть алгоритма в том, чтобы разложить все числа на множители, убрать лишние и затем их перемножить.
"Продвинутый" вариант программы
В функции main() создал массив для хранения множителей и заполнил его нулями.
count - является счетчиком количества записанных в массив множителей.
В функцию splitNumb() передаётся числа от 2 до 20, в ней они раскладываются на множители и заносятся в массив.
Использование указателей как параметров, передача массивов в функции и зачем все это нужно (немного теории)
Переменные создаваемые в функции являются локальными и не могут использоваться вне ее пределов. Когда из функции main() передается аргумент в другую функцию в них обоих создаются две разные переменные (каждая из которых занимает память) и из одной в другую копируются данные.
Чем это плохо? Место эти переменные занимают не абы где, а в стековом фрейме имеющем весьма ограниченный объем. Плюс операции копирования данных занимают время. То что некритично для небольших объемов данных (да и в нашем случае, думаю, это еще не сильно влияет) станет мешать при их увеличении.
Каждая переменная имеет свой адрес и к ней можно обращаться напрямую через указатели.
Так в нашем случае массив ar[100] и переменная count создаются в функции main() и в при вызове функции splitNumb() предаются лишь указатели на них. Функция splitNumb() через указатели напрямую обращается к областям памяти, в которых находятся эти данные и меняет их непосредственно там.
Это позволяет не дублировать данные и не передавать их туда-сюда, что ускоряет работу, но самое главное, что работа с локальными переменными одной функции из другой в принципе возможна лишь через указатели.
Что передается в функцию:
splitNumb(ar, sizeof(ar)/sizeof(*ar), &count, num);
ar - имя массива само по себе является указателем и указывает на адрес начала массива.
sizeof(ar)/sizeof(*ar) - вычисляется длина массива (100). Где:
- sizeof() - операция, возвращающая размер элемента в байтах;
- sizeof(ar) - возвращает количество байт, занимаемых массивом (400 байт в данном случае);
- sizeof(*ar) - возвращает количество байт, занимаемых первым элементом массива (4 байта в данном случае);
- Поясню, что значит *ar:
ar - это адрес в памяти первого элемента массива.
*ar - возвращает (по адресу) первый элемент массива (массив имеет элементы типа int) размер которого 4 байта.
&count - возвращает адрес переменой count.
num - число, которое нужно разложить на множители.
Функция, раскладывающая число на множители
В cnt принимается количество уже занесенных в массив множителей (count), чтобы новые множители заносились в следующие ячейки памяти массива и не затирали ранее внесенные множители.
Сначала переданное число проверяется на то, не делится ли оно нацело на множители, которые уже (после предыдущих итераций) содержатся в массиве. Если так, то оно делится на данный множитель и в дальнейшем мы уже работаем с новым (уменьшенным) числом. Этот этап необходим, чтобы убрать лишние множители.
Далее переданное число раскладывается на множители с помощью целочисленного деления, при этом множители заносятся в массив ar[] с помощью указателя на массив arr[].
Также меняется количество занесенных в массив множителей (счетчик count в функции main()) с помощью указателя на него *cnt_ptr.
Также необходимо постоянно следить (делать проверки) куда и что заносится.
if(cnt < lenght_arr) - проверка на не превышение длины массива. Если занести данные за пределами массива, они запишутся в область памяти, находящуюся за массивом и изменят данные, которые где-то вероятно были очень нужны, что может поломать не только программу, но при особом везении (и настойчивости) и компьютер.
Эта программа работает быстрее в два раза да и 0.5 секунды по большей части, я думаю, это работа самого VScode, а сама программа отработала почти мгновенно.
Несколько раз вычислил результат и время работы программы колеблется в районе 0.4 секунды.
Ответ на задачу:
P.S. Здесь Вы всегда можете посмотреть и обсудить мой вариант решения (но сначала лучше попробовать решить самостоятельно), задать вопрос “знатокам” или дать свой совет.
Также приглашаю всех на мой сайт)
На нем Вы можете посмотреть ответ на задачу Эйлера #5 (когда необходима лишь небольшая подсказка) и последний, самый быстрый вариант решения.
В общем, добро пожаловать на канал))