Rating@Mail.ru

Форум по операционной системе GNU/Linux и свободному программному обеспечению


Текущее время: 21 май 2018, 11:52

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу Пред.  1, 2
Автор Сообщение
Непрочитанное сообщениеДобавлено: 12 янв 2018, 16:00 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10718
Откуда: Харьков
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 КБ]
Скачиваний: 11
Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 12 янв 2018, 17:22 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10718
Откуда: Харьков
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
spy.png [ 26.44 КБ | Просмотров: 308 ]


Вариант решения - разбивать подгруппы можно только «снизу», иначе задача распадается на части и теряет смысл. Поэтому делать это будем на обратном ходе (возврате) рекурсивного обхода дерева:
Код:
#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 КБ]
Скачиваний: 11
Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 12 фев 2018, 15:36 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10718
Откуда: Харьков
Одна из лучших книг по алгоритмам и численным методам:
Цитата:
Хемминг Р.В.
Численные методы для научных работников и инженеров
Издательство Наука, 2-е издание
Год 1972

Из-за её давности (что никак не умаляет её достоинств :!: ) вы её вряд ли где можете купить...
А вот свободно её скачать (формат DJVU) можете здесь:
Изображение
Поспешите ... пока ещё лежит эта уникальная книжка.

Эта книга знаменита своим эпиграфом, который часто повторяют уже почти 50 лет ... давно уже забывши откуда это:
Цитата:
Цель расчетов — понимание, а не числа


P.S. (позже) Просто прикрепил скачанную книгу. ;-)


Вложения:
Хемминг Р.В. Численные методы для научных работников и инженеров (2-е издание, 1972).djvu [3.16 МБ]
Скачиваний: 1
Вернуться к началу
 Профиль Отправить личное сообщение  
 
 Заголовок сообщения: Re: алгоритмические трюки
Непрочитанное сообщениеДобавлено: 12 мар 2018, 00:03 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10718
Откуда: Харьков
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
sqrf.png [ 153.98 КБ | Просмотров: 231 ]
Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 13 май 2018, 12:59 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10718
Откуда: Харьков
Очень интересная и очень приятная в чтении книга:
Цитата:
Адитья Бхаргава, Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих
Серия «Библиотека программиста»
Перевел с английского Е. Матвеев

Изображение


Вложения:
Грокаем_Алгоритмы_Адитья_Бхаргава.pdf [11.92 МБ]
Скачиваний: 3
Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 13 май 2018, 14:22 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10718
Откуда: Харьков
Olej писал(а):
Очень интересная и очень приятная в чтении книга:

И ещё - Катрин Пассиг, Йоханнес Яёндер, Программирование без дураков
Цитата:
Изображение
ISBN: 978-5-496-02023-7
416 страниц
январь 2017
Питер

Цитата:
В большинстве случаев код намного легче писать, чем читать. Это связано с тем, что при написании кода у нас уже есть образная модель программы в голове — ее нужно лишь записать. Это «лишь записать» уже представляется довольно сложным делом. Однако для того, чтобы код, особенно чужой, прочитать и понять, нужно в процессе чтения суметь восстановить образную модель программы, существова­вшую в голове разработчика данного продукта, а это намного сложнее.


Вложения:
Пассиг_К_,_Яндер_Й_Программирование@itliba.PDF [10.12 МБ]
Скачиваний: 3
Вернуться к началу
 Профиль Отправить личное сообщение  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу Пред.  1, 2

Часовой пояс: UTC + 3 часа


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

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB
[ Time : 3.618s | 22 Queries | GZIP : On ]