Страница 5 из 5
Re: примеры задач при изучении C++
Добавлено: 09 июн 2017, 13:33
Olej
Olej писал(а):Вот ещё десятка 2 задач на использование STL / Boost, которая на сегодня (после C++03) является просто составной частью стандарта (стандартной библиотеки) C++ :
Начала STL и контейнры C++.
Объяснять не хочется ... кому нужно - посмотрит сам.
Вот хорошая задача
попалась:
Рассмотрим параллельную систему из m процессоров p1,p2,...,pm, выполняющую n независимых заданий t1,t2,...,tn с временами обработки a1, a2,…,an. Каждый процессор может выполнить любое задание, прерывания запрещены. Требуется указать оптимальное по быстродействию расписание без прерываний.
Сначала отсортируем a1, a2,…,an по убыванию. Далее на первые m процессоров загружаются первые m заданий, потом на первый освободившийся процессор задание t(m+1), на второй – t(m+2) пока не будут загружены все n заданий. Для исходного расписания считаем длину, т. е. для каждого процессора сумму aj и выбираем максимум среди всех процессоров
Хорошая не тем, что сложная - ничего сложного там нет - а тем, что даёт повод записать её
как можно более кратко через обобщённые алгоритмы STL.
Re: примеры задач при изучении C++
Добавлено: 09 июн 2017, 15:34
Olej
Olej писал(а):
Рассмотрим параллельную систему из m процессоров p1,p2,...,pm, выполняющую n независимых заданий t1,t2,...,tn с временами обработки a1, a2,…,an. Каждый процессор может выполнить любое задание, прерывания запрещены. Требуется указать оптимальное по быстродействию расписание без прерываний.
Сначала отсортируем a1, a2,…,an по убыванию. Далее на первые m процессоров загружаются первые m заданий, потом на первый освободившийся процессор задание t(m+1), на второй – t(m+2) пока не будут загружены все n заданий. Для исходного расписания считаем длину, т. е. для каждого процессора сумму aj и выбираем максимум среди всех процессоров
Хорошая не тем, что сложная - ничего сложного там нет - а тем, что даёт повод записать её
как можно более кратко через обобщённые алгоритмы STL.
Код: Выделить всё
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
inline ostream& operator <<( ostream& out, const vector<int>& obj ) {
copy( obj.begin(), obj.end(), ostream_iterator<int>( out, " " ) );
return out << endl;
}
int main( int argc, char *argv[] ) {
const int m = 3;
vector<int> p( m );
vector<int> a( { 20, 1, 2, 3, 10, 7, 13, 17 } );
cout << a;
sort( a.begin(), a.end(), greater<int>() );
cout << a;
while( !a.empty() ) {
*p.begin() += *a.begin();
cout << *a.begin() << " => " << p;
a.erase( a.begin() );
sort( p.begin(), p.end(), less<int>() );
}
cout << "максимальная длина = " << p.back() << endl;
}
И вот как это выполняется (с отладочными выводами ... без них вся программа вообще записывается в 8 строк):
Код: Выделить всё
[olej@dell queue]$ ./queue
20 1 2 3 10 7 13 17
20 17 13 10 7 3 2 1
20 => 20 0 0
17 => 17 0 20
13 => 13 17 20
10 => 23 17 20
7 => 24 20 23
3 => 23 23 24
2 => 25 23 24
1 => 24 24 25
максимальная длина = 25
Re: примеры задач при изучении C++
Добавлено: 13 июн 2017, 20:04
Olej
Вот ещё одна любопытная, как мне кажется, задачка:
Программа читает текстовый файл (имя с расширением .dat, заданное в командной строке запуска).
После этого программа:
- выводит текст на экран дисплея;
- определяет количество символов в каждом слове;
- выбирает для показа самое короткое слово;
- выбранное слово выделяется цветом в выводимом тексте;
- при очередном нажатии клавиши Enter выделение перемещается на следующее по длине слово.
Но, поскольку эта задача описана в отдельной теме, касающейся цвета вывода, то см. комментарии по ней там:
отображение цветом в терминале.
Re: примеры задач при изучении C++
Добавлено: 12 янв 2018, 15:16
Olej
Из совсем
простеньких задач (но тема то "при изучении"?):
В последовательности вводимых чисел удалить повторяющиеся совпадающие числа (серии), оставив на месте этих серий только одно вхождение повторяющегося числа.
Это может быть так:
Код: Выделить всё
#include <bits/stdc++.h>
using namespace std;
ostream& operator <<( ostream& out, const list<int>& obj ) {
out << "[ ";
for( auto i: obj ) cout << i << " ";
return out << "]";
}
void ddubl( list<int>& obj ) {
auto c = obj.begin(), n = c;
n++;
while( c != obj.end() ) {
if( *n == *c ) {
auto d = n;
n++;
obj.erase( d );
}
else {
c = n;
n++;
}
if( n == obj.end() )
break;
}
}
int main( int argc, char *argv[] ) {
list<int> lst;
while( true ) {
lst.clear();
string e;
getline( cin, e );
if( !cin || 0 == e.length() ) break;
istringstream ist( e );
int d;
while( ist >> d )
lst.push_back( d );
cout << lst << " => ";
ddubl( lst );
cout << lst << endl;
}
}
В коде применены расширения стандарта C++11, но это только "для красоты"
- для укорочения кода ... можете легко это устранить. Сборка:
Код: Выделить всё
[olej@dell dlist]$ g++ -Wall -std=c++11 -O3 dlist.cc -o dlist
Выполнение:
Код: Выделить всё
[olej@dell dlist]$ ./dlist
1 1 2 3 4
[ 1 1 2 3 4 ] => [ 1 2 3 4 ]
1 2 2 2 3 4 5 5 5 6
[ 1 2 2 2 3 4 5 5 5 6 ] => [ 1 2 3 4 5 6 ]
1 2 3 4 4 4 4
[ 1 2 3 4 4 4 4 ] => [ 1 2 3 4 ]