9д

Вычислительные алгоритмы

Задача о наполнении рюкзака
1) Дано N предметов K[i] с указанием веса W[i] и стоимости каждого предмета V[i]. Определить набор предметов T с максимальной стоимостью груза S, вес которого не больше P.
Алгоритм решения. 
Для решения этой задачи используем рекурсивный перебор вариантов для массива весов, проверяя условия на достижение оптимального веса P и максимальной стоимости S выбранных предметов из массива T. Каждый раз начинаем перебор с текущего предмета в массиве W. Для эффективного перебора необходимо отсортировать массив стоимостей по убыванию и затем для одинаковых значений стоимостей массив весов сортируем по возрастанию, например, по методу пузырька.

2) Грабитель, проникший в банк, обнаружил в сейфе k золотых слитков, массами w1, w2, ..., wk килограмм. При этом грабитель может унести не более W килограмм. Определите набор слитков, который должен взять грабитель, чтобы унести как можно больше золота. (http://informatics.mccme.ru/mod/book/view.php?id=815&chapterid=60)

3) В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каж дого номинала неограничен. (http://informatics.mccme.ru/mod/book/view.php?id=815&chapterid=59)

Задача о поиске пути в лабиринте
Дана схема лабиринта в виде матрицы чисел из 0 и 1. Найти наименьшую длину пути и направление движения выхода из лабиринта, если это возможно.
Волновой алгоритм. 
Пометим сначала все свободные пути лабиринта нулями. Стартовую точку входа пометим единицей. Далее на каждой итерации выполняем действия:
- найти в лабиринте свободное место, помеченные 1;
- для каждой из четырех соседних с ней свободных мест проверяем два условия: помечена ли она нулем и есть ли стена между двумя свободными местами (выбранной и соседней);
- Если оба условия выполнены, помечаем соседнее свободное место двойкой. И переходим к следующей итерации, т.е. начинаем поиск с 2 и т. д.
Рекурсивный алгоритм. 
Начинаем с текущей точки (х, у), которую помечаем 2. Смотрим вокруг точки (слева, справа, сверху, снизу) - если стенки нет, то устанавливаем 2 и вызываем рекурсивно эту же функцию с новыми координатами, иначе - возвращаемся назад. Если перешли в точку выхода, то конец алгоритма. Данный алгоритм плохо работает тогда, когда существуют тупики или выхода нет.
Задача о коммивояжере
1) Сформировать оптимальный маршрут объезда n городов. Необходимо выбрать один лучший из (n-1)! вариантов по критерию времени, стоимости или длине маршрута.

2) Дана неотрицательная матрица размера n×n, где элемент в i-й строке и j-ом столбце соответствует стоимости выполнения j-ого вида работ i-м работником. Нужно найти такое соответствие работ работникам, чтобы расходы на оплату труда были наименьшими. 
Венгерский метод.
Если цель состоит в нахождении назначения с наибольшей стоимостью, то решение сводится к решению только что сформулированной задачи путём замены каждой стоимости C на разность между максимальной стоимостью и C.
Алгоритм основан на двух идеях:
- если из всех элементов некоей строки или столбца вычесть одно и то же число y, общая стоимость уменьшится на y, а оптимальное решение не изменится;
- если есть решение нулевой стоимости, оно оптимально.
Алгоритм ищет значения, которые надо вычесть из всех элементов каждой строки и каждого столбца (разные для разных строк и столбцов), такие что все элементы матрицы останутся неотрицательными, но появится нулевое решение.

3) Известны, что все транспортные расходы от одного города до другого неотрицательны. Найти наименьшую стоимость проезда из 1-го города в k-ый.
Алгоритм Дейкстры. 
В процессе работы алгоритма некоторые города будут выделенными :
- для каждого выделенного города i хранится наименьшая стоимость пути; при этом известно, что минимум достигается на пути, проходящем только через выделенные города;
- для каждого невыделенного города i хранится наименьшая стоимость пути, в котором в качестве промежуточных используются только выделенные города.
Множество выделенных городов расширяется на основании следующего замечания: если среди всех невыделенных городов взять тот, для которого хранимое число минимально, то это число является истинной наименьшей стоимостью.
Добавив выбранный город к выделенным, мы должны скорректировать информацию, хранимую для невыделенных городов. При этом достаточно учесть лишь пути, в которых новый город является последним пунктом пересадки, а это легко сделать, так как минимальную стоимость проезда в новый город мы уже знаем.
Алгоритм Флойда.
Перенумеровать вершины графа от 1 до N целыми числами, определить матрицу D, каждый элемент d[i,j]  которой есть длина кратчайшей дуги между вершинами i и j. Если такой дуги нет, положить значение элемента равным ∞. Кроме того, положить значения диагонального элемента d[i,i] равным 0.
Для целого m, последовательно принимающего значения от 1 до N определить по элементам матрицы D элементы матрицы B: bi,j=min( di,m+ dm,j; di,j ).
Затем переприсвоим значения матриц:  di,j=bi,j.
Алгоритм заканчивается получением матрицы D.

Задача о расстановке шахматной фигуры
1) Известно местоположение белого и черного коня. Нужно узнать, за какое наименьшее число ходов белый конь срубит черного, если тот будет стоять на месте.
Рекурсивный алгоритм.
Рекурсивно будем переходить на 8 известных перемещений коня, считая каждый раз количество проходов. Если во время прохода мы дойдем до местоположения черного коня, то это количество нужно сравнить по минимуму с уже найденным. Если такого пути найти не удается, то вывести сообщение «No solution».

2) Известно, что на доске 8×8 можно расставить 8 ферзей так, чтобы они не били друг друга. Вам дана расстановка 8 ферзей на доске, определите, есть ли среди них пара бьющих друг друга.
Алгоритм решения:
Заполним массив нулями. Там, где стоит ферзь - поставим 1. Вычисляем суммы по вертикалям, по горизонталям и по диагоналям (параллельно главной и побочной) - они должны быть не больше 1.

Задача о построении выпуклой оболочки
Даны точки на плоскости. Построить по этим точкам выпуклый многоугольник.
1) По вычислению ориентированной площади. 
Все треугольники, образованные тройками соседних вершин в порядке их обхода, имеют одну ориентацию. Просматривая все тройки точек по очереди, вычисляем ориентированную площадь треугольника по трем точкам (знак которой определяется при вычислении): S = ((x1-x3) y2 + (x3-x2) y1+ (x2-x1) y3)/2.
Если ориентация точек не совпадает с заданной (по часовой стрелке), то точка лежит вне  многоугольника.
2) Алгоритм Грэхема. 
Пусть найден центр тяжести всех координат. Упорядочим точки относительно полярного угла (можно сравнивать сумму абсолютных значений координат). 
Так как внутренние точки принадлежат некоторому треугольнику, то будем последовательно просматривать отсортированный массив и удалять внутренние вершин. Оставшиеся точки будут являться вершинами выпуклой оболочки.
3) Алгоритм Джарвиса.  
Отрезок, определяемый двумя точками, является ребром выпуклой оболочки тогда и только тогда, когда все другие точки множества лежат на отрезке или с одной стороны от него. Для каждого из этих отрезков можно определить положение остальных N-2 точек относительно него, так чтобы угол, образованный лучами имел минимальное значение. Если таких точек несколько, то выбирается точка, находящаяся на максимальном расстоянии от текущей. Таким образом, можно найти все пары точек, определяющих ребра выпуклой оболочки. 
4) Алгоритм «разделяй и властвуй». 
Исходное множество из N точек разбивается на два подмножества, каждое из которых будет содержать одну из двух ломаных, которые при соединении образуют выпуклую оболочку.  Для начала нужно определить две точки, которые будут являться соседними вершинами выпуклой оболочки. Проведем прямую через эти две точки. Нужно найти точку максимально удаленную от прямой. Все точки, лежащие в образованном треугольнике исключаются из дальнейшего рассмотрения. Остальные точки будут делиться на два подмножества: точки, которые лежать левее, и точки, которые лежат правее новых прямых. С каждым из подмножеств проделываем то же самое. Каждое из них содержит ломаные, которые и дают выпуклую оболочку. Это реализуется рекурсивной процедурой, которая для данного ей множества возвращает соответствующую часть выпуклой оболочки.

Ввод и вывод данных из файла

Если данных много или неизвестно сколько, то лучше их сохранить в текстовый файл в то же место, где находится файл main.cpp.

Пример 1. В текстовом файле записаны целые числа через пробел. Определить, сколько там чисел? Вывести все числа на экран.

#include <iostream>
#include <fstream> // библиотека для работы с файлами
#include<locale.h>

using namespace std;

int main()
{
    setlocale (LC_ALL,"Russian");
    ifstream fin("file.txt"); //объявляем файловую переменную и связываем ее с файлом file.txt
    int a[100],i=0;
    while(fin>>a[i]) //пока еще есть числа в файле сохраняем в массив
    {
        cout<<a[i]<<" "; //вывод на экран
        i++; // увеличиваем счетчик чисел
    }
    cout<<"\n всего чисел="<<i;
    return 0;
}

Пример 2. В текстовом файле хранится размер двумерного массива и сами элементы массива.
3 3
1 2 3 
4 5 6 
0 1 2 
Вывести в другой файл все элементы массива.

#include <iostream>
#include <fstream>

using namespace std;
int main()
{
    ifstream fin("file.txt");
    int n,k,i,j;
//вводим из файла два числа: количество строк и столбцов в массиве
    fin>>n>>k;
//задаем двумерный массив и заполняем его из файла
    int a[n][k];
    for (i=0;i<n;i++)
    {
        for (j=0;j<k;j++)
        {
            fin>>a[i][j];
        }
    }

//объявляем файловую переменную для вывода и связываем с файлом result.txt

    ofstream fout("result.txt");
//выводим массив в файл
    for (i=0;i<n;i++)
    {
        for (j=0;j<k;j++)
        {
            fout<<a[i][j]<<" ";
        }
        fout<<endl;
    }
    fout.close(); //закрываем файл 
    return 0;
}
Упражнение:

  1. Задан размер двумерного массива, например: 3 4. Получить массив в виде
    1 2 3 4
    5 6 7 8
    9 10 11 12
  2. Задан размер двумерного массива, например: 6 5. Получить массив в виде
    1 1 1 1 1
    1 0 0 0 1
    1 0 0 0 1
    1 0 0 0 1
    1 1 1 1 1
  3. Заданы в текстовом файле числа 0 и 1 через пробел. Вывести в другой файл сначала все 0, затем все 1.
  4. Заданы в текстовом файле числа 2 и 1 через пробел. Вывести в другой файл сначала все 2, затем все 1.
Домашнее задание: на http://informatics.mccme.ru/ выполнить задания №1589, 1590, 1591

Моделирование физических процессов (ФТ)

  1. Взлет ракеты - Цвенгер
  2. Выстрел из пушки - Кулумбегов
  3. Движение планет и спутников - Шаповалов
  4. Столкновение заряженных частиц - Чупрунов
  5. Свободное колебание маятника - Грачева
  6. Затухающее колебание маятника - Саранцева
  7. Распространение тепла в стержне - Фокт
  8. Распространение звуковой (водной) волны - Ганеев
  9. Изображение электрических полей - Карабанов
  10. Падение парашютиста
  11. Движение груза, привязанного на пружине 
  12. Движения груза по наклонной поверхности
Компьютерное моделирование (Майер Р.В.)

Игровые стратегии (ИТ)

1 этап - вывести игровое поле, если нужно - предварительно его создать, используя генерацию случайных чисел (например, в игре сапер)
2 этап - написать алгоритм хода игрока и хода компьютера
3 этап - написать алгоритм проверки состояния игры: Победа, Проигрыш, Ничья.
4 этап - проверить игру на разные входные данные от игрока, такие как "защита от дурака", ход повторяется, пропуск хода, завершить игру и т. д.
  1. Ханойская башня
  2. Пятнашки
  3. Крестики-нолики
  4. Сапер
  5. Морской бой
  6. Судоку
  7. Четыре в ряд
  8. Быки и коровы (игра с числами)
  9. Шашки
  10. Шахматы
  11. Найти пару
  12. Реверси
  13. Хексагон
  14. Игра в точки
  15. Тетрис
  16. Пасьянс
  17. Карточные игры
  18. Шарики в линию
  19. Эрудит (игра в слова)
#include <stdlib.h>
#include <time.h>

srand(time(NUUL));//генератор случайных чисел
int i=rand()%3 // случайное число от 0 до 2
int A[8][8] // шахматное поле в виде двумерного массива
//вывод игрового поля
for (int i =0; i<10; i++)
{
   for (int j =0; j<10; j++)
      cout<<A[i][j]<<" ";
   cout<<endl;
}
//генерация игрового поля случайным образом
int x, y;
do
{
  x=rand()%3 ;
  y=rand()%3;
  if (A[x][y]==0) { A[x][y]=10; break;}
}while (true)

Анимация объектов

Из задания 1 определите спрайт (героя, фигуру), который вы хотите переместить. Выполнить один из пунктов 1-6 в Задание 3. Программу загрузить в свою папку на Google диске и ссылку разместить в Таблицу продвижения. 

Построение графика функции

Вставить фрагмент программы из Задания 2 в свой шаблон для вывода графики.
Оформите отдельно в виде процедуры grafik_func(int pa, int pb, int pc, int pd, double a, double b, double ymin, double ymax) и вызовите еев главной программе после инициализации графического экрана.

Записать свою функцию myfunc(x) для построения графика. Примеры функций:
  1. y=x*sin(x)
  2. y=sin(x)*cos(x)
  3. y=sin(x)+cos(x)
  4. y=exp(sin(x))
  5. y=x*x*(x-2)*(x-2)
  6. y=2*x*x*x+3*x*x-5
Написать функцию нахождения минимального (minimumfunc(a,b);) и наибольшего (maximumfunc(a,b);) значения функции и передать их в переменные ymin и ymax соответственно.

Домашнее задание от 14.11.14:

Выполнить 1-6 пункты Задания 2 с использованием процедур и функций. Программу загрузить в свою папку на Google диске и ссылку разместить в Таблицу продвижения. 

Функции и процедуры в С++

В программе можно выделить часть повторяемого кода в отдельный блок - подпрограмму.
Подпрограмма - это вспомогательная программа, которая может быть использована в друой программе один или несколько раз.

Так же как и главная программа - в подпрограмме можно использовать входные и выходные данные. Если результат вычисления подпрограммы нужно запомнить и использовать в других выражениях, то лучше оформить это как функция, заисящая от параметров. Например, стандартные математические функции sin(x), cos(x), pow(a,n) - возвращают (вычисляют) значения. В С++ главная программа main сама является функцией без параметров и возвращает код завершения программы: если удачно, то 0, иначе - код ошибки.

Как построить свою функцию в С++?

<тип возвращаемого значения> имя_функции(<тип параметра 1> имя_переменной, <тип параметра 2> имя_переменной, ..., <тип параметра k> имя_переменной)
{
    <тело функции>
    return <возвращаемое значение>;
}

Например:
double tg(double x)
{
    return sin(x)/cos(x);
}
Если параметров нет, то используют ключевое слово void, либо пустые скобки.

Как вызвать функцию в главной программе?

int main()
{
    double x;
    cout<<tg(2)+tg(5)<<endl;
    cin>>x;
    double y= tg(2*x);
    cout<<y<<endl;
}

Вызов функции без параметров ничем не отличается от вызова функции с параметром, только в списке ничего не пишут (даже void!). Но скобки нужно ставить ОБЯЗАТЕЛЬНО!

Если функция ничего не возвращает, то вместо типа пишут ключевое слово void. Тогда такую функцию будем называть процедурой.

Например, процедура инициализации графического режима:
     
void intgr()
{ 
   int gdriver = DETECT, gmode, errorcode;
   initgraph(&gdriver,&gmode,"");
}
 
Если функций и процедур много и их хочется повторить в другой программе,
то их можно выделить в отдельный файл и подключить с помощью директивы #include.

Если файл находся в папке include, то его подключают так:
#include <math.h>



Если файл разместить в папке проекта, то так:


#include "mymath.h"








Блог-урок "Компьютерная графика в С++"



http://computer-graphics-in-c.blogspot.ru/



Домашнее задание от 17.11.14/31.11.14:

Выполнить Задания 1. Программу загрузить в свою папку на Google диске и ссылку разместить в Таблицу продвижения. 



Вспомним программирование на С++

Презентации

Таблица соответствия команд Кумир и С++

Строки в С++

Массивы

STL (для олимпиадников)



Домашнее задание от 19.09.2014



На сайте informatics.mccme.ru в разделе "Типы данных" решить по 2 задачи на темы:



- Целые числа



- Символы и строки



- Действительные числа






































































Комментариев нет
                                      :
                                    
















Отправить комментарий




















                                      

                                    









Подписаться на:

Сообщения
                                      (
                                      Atom
                                      )