Thinker - Форум программистов и сисадминов Киберфорум

Thinker

Форум программистов и сисадминов Киберфорум

Войти

Регистрация
Восстановить пароль

Рекурсивные комбинаторные алгоритмы

Запись от Thinker размещена 10.07.2013 в 10:27. Обновил(-а) Thinker 10.07.2013 в 19:12

Показов 5083 Комментарии 2

Задача о бандероли
За пересылку бандероли надо уплатить 100 рублей. Сколькими способами можно оплатить ее марками стоимостью 1,2,3,5 рублей, если два способа, отличающиеся порядком марок, считаются различными (запас марок различного достоинства считаем неограниченным).
Используем рекурсивную функцию
F(n) = F(n-1) + F(n-2) + F(n-3) + F(n-5)
с начальными условиями
F(0) = 1,
F(x) = 0 при x < 0
получается 117372865913707249 способов. обычной рекурсией его не получить. Только с сохранением уже подсчитанного:

Кликните здесь для просмотра всего текста

C++

1	#include<iostream>

...

Thinker

Размещено в Без категории

Быстрый алгоритм Евклида вычисления НОД

Запись от Thinker размещена 10.07.2013 в 10:03

Показов 2076 Комментарии 0

Заинтересовал вопрос о различных реализациях алгоритма Евклида для неотрицательных целых чисел. Ниже привожу алгоритмы, собственноручно написанные, исходя из теоретического материала. Каждый алгоритм можно модифицировать в ту или иную сторону.

Считается, что бинарный алгоритм работает быстрее, но тесты показывают, что во многих случаях два первых алгоритма работают быстрее бинарного.
1. обычный алгоритм Евклида через остатки

Кликните здесь для просмотра всего текста

C++

long Nod(long a, long b)
{
    while (a && b)
        if (a >= b)
           a %= b;
        else

...

Thinker

Размещено в Без категории

Быстрое нахождение суммы делителей натурального числа

Запись от Thinker размещена 10.07.2013 в 09:58. Обновил(-а) Thinker 11.07.2013 в 09:55

Показов 2324 Комментарии 0

Приведу быстрый алгоритм нахождения суммы делителей. Сумма ищется по формуле
$https://www.cyberforum.ru/cgi-bin/latex.cgi?S(a) = \frac{p_1^{a_1+1}-1}{p_1-1}\cdot\frac{p_2^{a_2+1}-1}{p_2-1}...\cdot\frac{p_n^{a_n+1}-1}{p_n-1}$ , где
$https://www.cyberforum.ru/cgi-bin/latex.cgi?a=p_1^{a_1}...p_n^{a_n}$ - каноническое разложение числа a.

Кликните здесь для просмотра всего текста

C++

unsigned long Sum(unsigned long a)
{
   unsigned long sum = 1, k = 1, i;
   if (a == 1)
      return a;
   while ((a & 1) == 0)
   {
      k <<= 1;
      a >>= 1;
   }
   k = (k << 1) - 1;
   if (a == 1)
      return k;
   else

...

Thinker

Размещено в Без категории

Быстрое нахождение количества делителей натурального числа

Запись от Thinker размещена 10.07.2013 в 09:54. Обновил(-а) Thinker 11.07.2013 в 09:55

Показов 2210 Комментарии 0

Часто требуется найти количество делителей натурального числа и, по возможности, это надо осуществить очень быстро. В следующем быстром алгоритме количество делителей ищется по формуле
$https://www.cyberforum.ru/cgi-bin/latex.cgi?count(a) = (a_1+1)(a_2+1)...(a_n+1)$ , где
$https://www.cyberforum.ru/cgi-bin/latex.cgi?a=p_1^{a_1}...p_n^{a_n}$ - каноническое разложение числа a.

Кликните здесь для просмотра всего текста

C++

// быстрый алгоритм без использования дополнительной памяти
unsigned long Count(unsigned long a)
{
   unsigned long count = 1, k = 0, i;
   if (a == 1 || a == 2)
      return a;
   while ((a & 1) == 0)

...

Thinker

Размещено в Без категории

Быстрая проверка натурального числа на простоту

Запись от Thinker размещена 10.07.2013 в 09:49

Показов 3653 Комментарии 0

Часто возникает задача проверки натурального числа на простоту. При этом имеются вероятностные и детерминированные методы проверки. Здесь рассматриваются только детерминированные алгоритмы, дающие 100% ответ на вопрос о простоте.

Хорошо известно такое утверждение: если натуральное число n>1 не делится ни на одно простое число, не превосходящее , то оно простое. В связи с этим получается самый простой способ проверки на простоту алгоритм

Кликните здесь для просмотра всего текста

C++

int Prime(unsigned long a)
{
   unsigned long i;
   if (a == 2)
      return 1;
   if (a == 0 || a

...

Thinker

Размещено в Без категории

Thinker

Регистрация 26.08.2011
Адрес Приволжский ФО
Сообщений 3,802
Записей в блоге 5

Поиск в блоге Thinker

Содержит текст: Искать только в заголовках

Расширенный поиск
Категории блога
Локальные категории
- Без категории
Последние комментарии
- Рекурсивные комбинаторные алгоритмы автор: Thinker
Последние записи
Последние посетители
- Argus19 (20.11.2024, 12:47)
- Catstail (07.03.2024, 11:43)
- gunslinger (27.01.2024, 13:32)
- igorrr37 (29.12.2023, 08:16)
- mine1 (13.04.2023, 11:57)
- plug1 (05.11.2022, 15:24)
- ShestakobDI (06.09.2023, 19:43)
- ValeriyKrazin (20.11.2022, 23:18)
Облако меток

.net .net core .net core 9 1с 7z access ai android android api angroid angular apache api apollo apple archive arduino asm asp.net asp.net core assembler astra linux async azure bash basic bios blu-ray bot c c# c# 12 c++ chatgpt ci/cd cmake cmd com compose console cpu cqrs crud css cuda db deb builder debian delphi denwer devops di diy docker doom dotnet dry dto dvd elk excel f# fedora firebird fpga fps freebasic game gamedev gimp git github gitlab gnome go goa gof golang gpgpu gpt gpu gradle deb grafana graphql grpc haskell hcl notes hdd home hotchocolate htaccess html html5 http i2c ide ios ipad iphone java javascript jenkins jquery js json jwt kafka kde keras kerio kotlin kubernetes kubuntu lazarus linux lisp lua mail make own deb manjaro matplotlib media mediatr meeting mime minecraft mingw mint ml mobile mpi msa ms access mvc mvp mvvp mysql network nginx npe null nullable nullreferenceexception numpy object c openai opencv opengl openmp openserver orm owen owenlogic pagination pandas parallel php php. laravel poco postgres postgresql postman powershell primevue programming prometheus pygame pyqt5 python python 3 pytorch qss qt qt creator qt designer r rabbitmq react redis rest restapi rest api restful risc-v robot robotics rust scala scheme scikit-learn scipy script-fu sdl seaborn senior senior developer sfml shell shell32 signalr soa solid spring ssd stm32 style subversion svn swagger swift tasm tcl telegram telegram bot tensorflow tetris tkinter typescript ubuntu ue unity unity3d unreal engine usb userscript vb vba victoria virtual machine visual studio void vue vue.js vue.js 3 vuejs web api webapi winapi windows windows 12 winforms wshshell xampp yandex yii2 zip zookeeper ассемблер база данных базы данных бд игровой пк ии кипиа компьютер курсы литература микроконтроллеры микросервисы мк монолит нейросети нейросеть новый год ооп оптимизация паттерны пк праздник процессоры регистр рождество си созвон сумматор тетрис триггер форум

Поиск по метке

Архив
< Январь 2025
Вс	Пн	Вт	Ср	Чт	Пт	Сб
22	23	24	25	26	27	28
29	30	31	1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31	1

Новые блоги и статьи
Какая разница между операторами == и === в сравнениях в JavaScript bytestream 21.01.2025 В мире веб-разработки JavaScript занимает особое место как динамический язык программирования, предоставляющий разработчикам широкий набор инструментов для создания интерактивных веб-приложений. . . .	Из чего и как собрать свой домашний кинотеатр bt_guru 21.01.2025 Создание домашнего кинотеатра: от идеи до реализации В современном мире домашний кинотеатр стал неотъемлемой частью комфортного жилого пространства, предоставляя возможность наслаждаться. . .	Ошибки стиральных машин bt_guru 21.01.2025 Современные стиральные машины представляют собой сложные электронные устройства, оснащенные множеством датчиков и систем контроля. Они способны самостоятельно определять вес загруженного белья,. . .	Копирование (маппинг) объектов в JavaScript bytestream 21.01.2025 В современной разработке программного обеспечения копирование объектов представляет собой фундаментальную операцию, которая требует особого внимания и понимания. Маппинг объектов в JavaScript – это. . .	Как работать с Apache Kafka в C# .NET bytestream 21.01.2025 Apache Kafka представляет собой распределенную платформу потоковой передачи данных, которая произвела революцию в области обработки больших объемов информации в реальном времени. Эта система,. . .	Как использовать RabbitMQ в C# .NET bytestream 21.01.2025 RabbitMQ представляет собой мощный брокер сообщений, который эффективно решает эту задачу, обеспечивая надежную передачу данных между множеством приложений. Этот инструмент реализует протокол AMQP. . .
Как объединить последние коммиты в Git bytestream 21.01.2025 В мире разработки программного обеспечения система контроля версий Git стала незаменимым инструментом для управления исходным кодом. Одной из наиболее полезных, но порой сложных для освоения функций. . .	Как запушить новую локальную ветку (branch) в удалённый репозиторий Git и отслеживать её bytestream 21.01.2025 В современной разработке программного обеспечения система контроля версий Git стала неотъемлемым инструментом для эффективного управления кодом и организации командной работы. Одной из ключевых. . .	Как создать директорию и все родительские директории, указанные в пути, с помощью Python bytestream 21.01.2025 Python предоставляет мощные инструменты для работы с файловой системой через встроенные модули os и pathlib, которые значительно упрощают процесс манипуляции директориями. Эти модули содержат. . .	Как работать с массивами в JavaScript bytestream 21.01.2025 Массивы в JavaScript представляют собой один из фундаментальных типов данных, который позволяет хранить упорядоченные коллекции различных элементов в одной переменной. Эта структура данных является. . .	Какая максимальная длина адреса (URL) в различных браузерах и стандартах bytestream 21.01.2025 В современном мире интернет-технологий URL-адреса (Uniform Resource Locator) играют фундаментальную роль в функционировании веб-пространства. Эти уникальные идентификаторы ресурсов стали неотъемлемой. . .	Как сбросить локальный репозиторий до состояния удалённого репозитория Git bytestream 21.01.2025 При разработке программного обеспечения с использованием системы контроля версий Git разработчики часто сталкиваются с необходимостью синхронизации локального и удаленного репозиториев. Данная задача. . .

Наверх

Сообщение форума

Отменить изменения