алгоритмы и алгоритмические трюки

Вопросы написания собственного программного кода (на любых языках)

Модератор: Olej

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: алгоритмы и алгоритмические трюки

Непрочитанное сообщение Olej » 12 янв 2018, 16:00

Olej писал(а): Вариант жадных алгоритмов
Задача №1 (заимствовано из каких-то учебных заданий):
В колонии на осваиваемой планете решили выбрать органы управления. Каждый из его жителей организовал партию, которую сам и возглавил. Отметим, что, ко всеобщему удивлению, даже в самой малочисленной партии оказалось не менее двух человек. К сожалению, финансовые трудности не позволили создать парламент, куда вошли бы, как предполагалось по правилам, президенты всех партий. Посовещавшись, колонисты решили, что будет достаточно, если в парламенте будет хотя бы один член каждой партии. Помогите организовать такой, как можно более малочисленный, парламент, в котором будут представлены члены всех партий.

Каждая партия и, соответственно, её президент имеют одинаковый порядковый номер от 1 до N (4 ⩽ N ⩽ 150). Вам даны списки всех N партий планеты.
Выведите предлагаемый вами парламент в виде списка номеров его членов.
Вариант решения:
- каждая партия представлена строкой номеров (вектор)
- ищем номер, который наиболее часто встречается во всех строках - включаем этот номер в результат
- очищаем все строки (вектора), куда входил выбранный номер
- повторяем с п.1 последовательно до тех пор, пока все строки станут пустыми

Код: Выделить всё

#include <bits/stdc++.h>
using namespace std;

ostream& operator <<( ostream& out, const vector<int>& obj ) {
   out << "[ ";
   for( auto i: obj ) cout << i << " "; 
   return out << "]";
}

ostream& operator <<( ostream& out, const vector< vector<int> >& obj ) {
   for( auto &x: obj ) 
      out << x << endl;
   return out; 
}
 
int main( int argc, char *argv[] ) {
   bool debug = argc > 1;
   vector< vector<int> > parts;
   int n = 0;
   while( true ) {
      string e;
      getline( cin, e );
      if( !cin || 0 == e.length() ) break;
      istringstream ist( e );
      int d;
      vector<int> line;
      while( ist >> d ) 
         line.push_back( d );
      if( find( line.begin(), line.end(), n + 1 ) == line.end() )
         line.push_back( n + 1 );
      parts.push_back( line );
      n++;
   } 
   vector<int> rezs( 0 );
   cout << parts;
   while( true ) {
      if( debug ) 
         cout << "-------------------------------" << endl << parts;
      vector<int> memb( parts.size() + 1, 0 );
      for( auto &x: parts ) 
         for( auto i: x )
            memb[ i ]++;          // частоты строк  
      auto mx = max_element( memb.begin(), memb.end() );
      if( 0 == *mx ) break;
      n = mx - memb.begin();      // самый частый номер
      rezs.push_back( n );
      if( debug ) cout << memb << " => " << *mx << " | " << n << endl; 
      for( auto x = parts.begin(); x < parts.end(); x++ )
         if( find( x->begin(), x->end(), n ) != x->end() )
            x->clear();          // очистить строки содержащие этот номер
   }
   cout << "результат: " << rezs << endl;
}
Выполнение:

Код: Выделить всё

[olej@dell part]$ ./part < p1.in
[ 1 2 ]
[ 2 4 6 7 ]
[ 3 6 7 ]
[ 4 5 7 ]
[ 5 6 ]
[ 6 4 ]
[ 7 5 ]
результат: [ 6 5 1 ]

[olej@dell part]$ ./part < p2.in
[ 2 4 7 1 ]
[ 4 6 7 5 2 ]
[ 3 6 7 ]
[ 4 5 7 1 ]
[ 5 6 2 3 ]
[ 6 4 7 1 ]
[ 7 5 2 ]
результат: [ 7 2 ]
Вложения
part.tgz
(2.76 КБ) 121 скачивание

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: алгоритмы и алгоритмические трюки

Непрочитанное сообщение Olej » 12 янв 2018, 17:22

Olej писал(а):
Olej писал(а): Вариант жадных алгоритмов
Задача №1 (заимствовано из каких-то учебных заданий):
Задача №2 (тоже заимствовано ... - но заимствования касаются только условий задач):
В некоторой Галактике силы правопорядка выявили разветвленную шпионскую сеть. Сеть сильно законспирирована и состоит из рядовых членов и руководителей различных уровней. Во главе стоит один руководитель — лидер. До начала арестов приказ лидера может быть доведен до любого члена сети. Все члены сети пронумерованы от 1 до N. Каждый член сети знает только своего вышестоящего руководителя (ровно одного) и своих непосредственных подчиненных (руководитель не знает подчиненных своего подчиненного и наоборот). Естественно, что с началом арестов членов сети она распадется на мелкие, не связанные друг с другом группы. Например, с арестом члена сети № 2 (на рисунке) сеть разваливается на 4 группы. Полицмейстер уверяет, что группа, состоящая из менее чем К членов сети, вырождается и не представляет угрозы. Стремясь не уронить престиж Галактики, полицмейстер поставил задачу произвести минимальное количество арестов членов сети так, чтобы от нее остались только вырождающиеся маленькие группы.
Требуется: Написать программу, которая бы по входным данным, описывающим структуру подпольной сети, выводила номера членов сети, которых нужно арестовать.
Входные данные: Входной файл содержит три строки. В первой записано число K (1≤K≤10 000), во второй строке — число N (1≤ N≤10 000), определяющее количество членов партии. Третья строка содержит набор из (N-1) числа. В этой строке для каждого члена партии, кроме лидера, задается номер его непосредственного руководителя. Номер руководителя всегда меньше, чем номер подчиненного. При этом первое число задает номер руководителя второго члена партии, второе — третьего и так далее. Числа в строке разделяются одним пробелом. Пример входного файла для структуры партии, представленной на рисунке:
3
14
1 1 2 2 3 2 3 6 6 6 7 4 7
Выходные данные: Выходной файл состоит из двух строк. В первую строку необходимо поместить количество арестов, а во вторую — номера членов сети, подлежащих аресту.
spy.png
Вариант решения - разбивать подгруппы можно только «снизу», иначе задача распадается на части и теряет смысл. Поэтому делать это будем на обратном ходе (возврате) рекурсивного обхода дерева:

Код: Выделить всё

#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

ostream& operator <<( ostream& out, const vector<int>& obj ) {
   out << "[ ";
   for( auto i = obj.begin(); i != obj.end(); i++ ) 
      out << *i << " ";
   return out << "]";
}

class tree : protected vector< vector<int> > {
public:
   vector<int> killed;
   tree( vector<int>& data ) {
      unsigned n = data.size() + 1;
      for( unsigned i = 0; i < n; i++ ) push_back( vector<int>( 0 ) );
      for( unsigned i = 0; i < data.size(); i++ ) {
         (*this)[ data[ i ] ].push_back( i + 2 ); 
      }
   }
   ~tree( void ) { for( auto &x: *this ) x.clear(); }
   friend ostream& operator <<( ostream& out, const tree& obj ) {
      for( unsigned i = 1; i < obj.size(); i++ )
         cout << i << "\t: " << ( obj[ i ] ) << endl; 
      return out;
   }
   int reduce( int k, int level = 1 ) {
      if( 1 == level ) killed.clear();
      if( (*this)[ level ].empty() ) return 1; // терминальная вершина
      int sum = 1;
      for( auto x: (*this)[ level ] )          // обход вниз не терминала
         sum += reduce( k, x );
      if( sum < k ) return sum;
      killed.push_back( level );
      (*this)[ level ].clear();
      return 0;
   }
}; 

int main( int argc, char** argv ) {
   bool debug = argc > 1;
   string e;
   int K, N;
   getline( cin, e );
   istringstream( e ) >> K; 
   getline( cin, e );
   istringstream( e ) >> N; 
   vector<int> line;
   getline( cin, e );
   istringstream sst( e );
   int d;
   while( sst >> d )
      line.push_back( d );
   if( debug )
      cout << "ввод: " << K << " | " << N << " | " << line << endl;
   tree t( line );
   if( debug ) cout << t;
   t.reduce( K );
   cout << "удалённых узлов " << t.killed.size() << " : " << t.killed << endl;  
}
Выполнение для дерева, показанного ранее в условии задачи (запустив программу с любым параметром, можно наблюдать промежуточную отладочную информацию хода выполнения):

Код: Выделить всё

[olej@dell spy]$ ./spy
3
14
1 1 2 2 3 2 3 6 6 6 7 4 7
удалённых узлов 4 : [ 7 2 6 1 ]
Как вариант, можно предположить возможность разбиения дерева на группы «сверху»:
- если у корневой вершины дерева M потомков, равное или больше K, то удаляем эту корневую вершину;
- при этом исходная сеть распадается на M автономных подсетей;
- рекурсивно применяем всё ту же процедуру последовательно для каждой из M подсетей;
Такой вариант реализации предлагается на самостоятельную проработку.
Вложения
spy.tgz
(28.88 КБ) 102 скачивания

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: алгоритмы и алгоритмические трюки

Непрочитанное сообщение Olej » 12 фев 2018, 15:36

Одна из лучших книг по алгоритмам и численным методам:
Хемминг Р.В.
Численные методы для научных работников и инженеров
Издательство Наука, 2-е издание
Год 1972
Изображение
Из-за её давности (что никак не умаляет её достоинств :!: ) вы её вряд ли где можете купить...
А вот свободно её скачать можете здесь:
https://ikfia.ysn.ru/wp-content/uploads ... 1972ru.pdf
Поспешите ... пока ещё лежит эта уникальная книжка.

Эта книга знаменита своим эпиграфом, который часто повторяют уже почти 50 лет ... давно уже забывши откуда это:
Цель расчетов — понимание, а не числа
P.S. (позже) Просто прикрепил скачанную книгу. ;-)
Вложения
Хемминг Р.В. Численные методы для научных работников и инженеров (2-е издание, 1972).djvu
(3.16 МБ) 142 скачивания

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: алгоритмические трюки

Непрочитанное сообщение Olej » 12 мар 2018, 00:03

Olej писал(а):
В этой статье мы поговорим о «магической» константе 0x5f3759df, лежащей в основе элегантного алгоритмического трюка для быстрого вычисления обратного квадратного корня.
По случаю, сделал этот алгоритм для Arduino, для совершенно другой процессорной архитектуры - AVR:

Код: Выделить всё

float FastInvSqrt( float x ) {
  float xhalf = 0.5f * x;
  uint32_t i = *(uint32_t*)&x;    // представим биты float в виде целого числа
  i = 0x5f3759df - ( i >> 1 );    // какого черта здесь происходит ?
  x = *(float*)&i;
  x = x * ( 1.5f- ( xhalf * x * x ) );
  return x;
}

void setup() {
  Serial.begin( 9600 );           // устанавливаем последовательное соединение
}

void loop() {
  uint32_t i = 0;                 // переменная для накопления числа
  while( Serial.available() > 0 ) // пока есть доступные данные
    i = i * 10 + ( Serial.read() - '0' );
  if( i != 0 ) {
    Serial.print( i, DEC );
    Serial.print( " => " );
    float s = 1. / FastInvSqrt( (float)i );
    Serial.println( s, 2 );
  }
  delay( 1000 );
}
На сегодня у меня не было под рукой живого (железного) Arduino ... поэтому сделал это в симуляторе: https://www.tinkercad.com.
Результат:

Код: Выделить всё

1000000 => 1001.70
10000 => 100.16
121 => 11.01
4 => 2.00
9 => 3.00
Вложения
sqrf.png

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: алгоритмы и алгоритмические трюки

Непрочитанное сообщение Olej » 13 май 2018, 12:59

Очень интересная и очень приятная в чтении книга:
Адитья Бхаргава, Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих
Серия «Библиотека программиста»
Перевел с английского Е. Матвеев
Изображение
Вложения
Грокаем_Алгоритмы_Адитья_Бхаргава.pdf
(11.92 МБ) 117 скачиваний

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: алгоритмы и алгоритмические трюки

Непрочитанное сообщение Olej » 13 май 2018, 14:22

Olej писал(а):Очень интересная и очень приятная в чтении книга:
И ещё - Катрин Пассиг, Йоханнес Яёндер, Программирование без дураков
Изображение
ISBN: 978-5-496-02023-7
416 страниц
январь 2017
Питер
В большинстве случаев код намного легче писать, чем читать. Это связано с тем, что при написании кода у нас уже есть образная модель программы в голове — ее нужно лишь записать. Это «лишь записать» уже представляется довольно сложным делом. Однако для того, чтобы код, особенно чужой, прочитать и понять, нужно в процессе чтения суметь восстановить образную модель программы, существова­вшую в голове разработчика данного продукта, а это намного сложнее.
Вложения
Пассиг_К_,_Яндер_Й_Программирование@itliba.PDF
(10.12 МБ) 112 скачиваний

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: алгоритмы и алгоритмические трюки

Непрочитанное сообщение Olej » 25 июн 2021, 15:48

Olej писал(а):
01 сен 2017, 19:38
По мотивам этой статьи можно построить и вычисление корня квадратного (без инверсии, 1/sqrt()):
Olej писал(а):
01 сен 2017, 19:33
Как легко видеть - точность быстрого вычисление не хуже 0.15% относительно точного значения.
Как определилось в тестах - C++ идиома pimpl - быстрота этого способа "очень сильно преувеличена".
Такая реализация может быть быстрой и эффективной только на малых встроенных устройствах с процессорами не имеющими команд вещественной арифметики.

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: алгоритмы и алгоритмические трюки

Непрочитанное сообщение Olej » 18 фев 2022, 12:41

Фундаментальная (491 стр.) книга по алгоритмам из самых разных областей (сведенных в единое внятное оглавление) + краткое описание алгоритмов + приведены реализации алгоритмов на C (кое-что на C++) + приводятся оценки вычислительной сложности O(N) - http://e-maxx.ru/upload/e-maxx_algo.pdf :
В этой книге Вы найдёте описание, реализации и доказательства множества алгоритмов, от известных всем до
тех, которые являются уделом лучших олимпиадников и специалистов по Computer Science. В конце приведены ссылки
на тематическую литературу, которую можно скачать с моего сайта, а также немного информации обо мне.
Шикарный справочник готовых реализаций несколько сот самых известных алгоритмов из разных областей математики!

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

алгоритмы и алгоритмические трюки

Непрочитанное сообщение Olej » 03 фев 2023, 18:20

Код: Выделить всё

olej@R420:~$ bc -i
bc 1.07.1
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006, 2008, 2012-2017 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'. 
11*11
121
111*111
12321
1111*1111
1234321
11111*11111
123454321
111111*111111
12345654321
1111111*1111111
1234567654321
11111111*11111111
123456787654321
111111111*111111111
12345678987654321
quit
:lol:
Нравится :?: :-o
Но ещё смешнее :lol: :

Код: Выделить всё

olej@R420:~$ python
Python 3.10.6 (main, Nov 14 2022, 16:10:14) [GCC 11.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> "{:X}".format(0x111*0x111)
'12321'
>>> "{:X}".format(0x1111*0x1111)
'1234321'
>>> "{:X}".format(0x11111*0x11111)
'123454321'
>>> "{:X}".format(0x111111*0x111111)
'12345654321'
>>> "{:X}".format(0x1111111*0x1111111)
'1234567654321'
>>> "{:X}".format(0x11111111*0x11111111)
'123456787654321'
>>> "{:X}".format(0x111111111*0x111111111)
'12345678987654321'
>>> "{:X}".format(0x1111111111*0x1111111111)
'123456789A987654321'
>>> "{:X}".format(0x11111111111*0x11111111111)
'123456789ABA987654321'
>>> "{:X}".format(0x111111111111*0x111111111111)
'123456789ABCBA987654321'
>>> "{:X}".format(0x1111111111111*0x1111111111111)
'123456789ABCDCBA987654321'
>>> "{:X}".format(0x11111111111111*0x11111111111111)
'123456789ABCDEDCBA987654321'
>>> "{:X}".format(0x111111111111111*0x111111111111111)
'123456789ABCDEFEDCBA987654321'
>>> quit()
Или ... кому ближе 8-ричная система:

Код: Выделить всё

olej@R420:~$ python
Python 3.10.6 (main, Nov 14 2022, 16:10:14) [GCC 11.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> "{:o}".format(0o1111*0o1111)
'1234321'
>>> "{:o}".format(0o11111*0o11111)
'123454321'
>>> "{:o}".format(0o111111*0o111111)
'12345654321'
>>> "{:o}".format(0o1111111*0o1111111)
'1234567654321'
>>> quit()

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

алгоритмы и алгоритмические трюки

Непрочитанное сообщение Olej » 18 май 2023, 12:40


Свободно скачивается, и, пожалуй, в этом есть смысл...

Код: Выделить всё

olej@R420:~/Книги/IT-книги/parallels$ ls -l Параллельные\ методы\ и\ алгоритмы.pdf 
-rw-rw-r-- 1 olej olej 5439324 мая 18 12:34 'Параллельные методы и алгоритмы.pdf'
МОСКВА
МАДИ
2020

Ответить

Вернуться в «Программирование»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 5 гостей