Задачи на моделирование

Проведение аналогий часто приводит к важным открытиям. Сравнив не совсем понятное явление с чем-то похожим, но более понятным, вы можете догадаться, как справиться с проблемой. Такое использование метафор называется «моделированием».

С. Макконелл, «Совершенный код»

Невозможно представить себе современную науку без широкого применения математического моделирования. Сущность этой методологии состоит в замене исходного объекта его "образом" — математической моделью — и дальнейшем изучении модели с помощью реализуемых на компьютерах вычислительно-логических алгоритмов. Этот метод познания, конструирования, проектирования сочетает в себе многие достоинства и теории, и эксперимента. Работа не с самим объектом (явлением, процессом), а с его моделью дает возможность безболезненно, относительно быстро и без существенных затрат исследовать его свойства и поведение в различных ситуациях (преимущества теории). В то же время вычислительные эксперименты с моделями объектов позволяют подробно и глубоко изучать объекты в достаточной полноте, недоступной чисто теоретическим подходам (преимущества эксперимента).

Задача №188.  Волшебная трава

Волшебная трын-трава, которую, как известно, косят зайцы строго в полночь, обладает следующими свойствами. После первого года жизни растение даёт 2 новых побега. Прожив 2 года, каждое растение пускает 4 новых побега, а после трёх лет еще 5 новых растений. Растения, достигшие четырёх лет жизни, скашивают зайцы. Выясните, сколько растений K трын-травы будет на поле спустя N лет, если изначально посадили одно растение.

Входные данные

Одно целое неотрицательное число N≤30

Выходные данные

Единственное число K–общееколичество растений.

Пример

Ввод	Вывод
4	139

Решение

Очевидно, что у нас имеется растения 4 категорий:

A0 – не достигшие одного года;

А1 – растения, прожившие 1 год;

А2 – растения, прожившие 2 года;

А3 – растения, прожившие 3 года.

Далее несложно моделировать процесс роста и старения растений

#include <iostream>

int main(){

unsigned long long n,a0=1,a1=0,a2=0,a3=0;

std::cin>>n;

for(int i = 1; i <= n; i++){

   a3 = a2;

   a2 = a1;

   a1 = a0;

   a0 = a1*2 + a2*4 + a3*5;

}

std::cout << a0 + a1 + a2 + a3 << "\n";

}

Задача №189.  Драконы (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Известно, что у дракона может быть несколько голов и его сила определяется числом голов. Но как определить силу драконьей стаи, в которой несколько драконов и у каждого из них определенное число голов? Вероятно, вы считаете, что это значение вычисляется как сумма всех голов? Это далеко не так, иначе было бы слишком просто вычислить силу драконьей стаи. Оказывается, что искомое значение равно произведению значений числа голов каждого из драконов. Например, если в стае 3 дракона, у которых 3, 4 и 5 голов соответственно, то сила равна 3*4*5 = 60. Предположим, что нам известно суммарное значение голов драконьей стаи, как нам вычислить максимально возможное значение силы этого логова драконов? Именно эту задачу Вам и предстоит решить.

Входные данные

В единственной строке записано натуральное число N (0 < N < 100) – количество голов драконьей стаи.

Выходные данные

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

Примеры

№	Ввод	Вывод
1	6	9
2	8	18
3	13	108

Решение

Легко по индукции убедиться, что наиболее сильная стая будет составлена из двухголовых и трёхголовых драконов. В самом деле, одноглавый дракон не увеличивает силу стаи, четырёхглавый эквивалентен двум двухголовым, пятиглавый – увеличивает меньше чем двуглавый вместе с трёхглавым. Далее, шестиглавый дракон увеличит мощь стаи меньше, чем два трёхголовых и т.д.

Таким образом, задача свелась к перебору возможных комбинаций стаи из двухголовых и трёхголовых драконов.

#include <iostream>

int main() {

int n, n2, n3, i;

std::cin >> n;

long long maxpwr = (!n ? 0 : 1), p;

for(n3 = n/3; n3+1; n3--){  //перебираем трёглавых драконов

   n2 = (n - n3*3) / 2;    //определяем число двуглавых

   p = 1;                  //текущая мощь стаи

   for(i = 1; i <= n3; i++) p *= 3;

   for(i = 1; i <= n2; i++) p *= 2;

   if(p > maxpwr) maxpwr = p;

}

std::cout << maxpwr;

}

Задача №190.  Считалочка

 В круге стоят N человек (см. рис.). Они пронумерованы от 1 до N. Поочередно из круга начинает выходить каждый K-й человек. Это продолжается до тех пор, пока в круге не останется последний человек. Определить его номер.

Например, если в круге стояло 7 человек и по считалке выходит каждый третий, то его поочерёдно покинут 3, 6, 2, 7, 5, 1. Оставшимся будет человек, стоявший на 4 месте.

Входные данные

В единственной строке файла count.in записаны два натуральных числа, не превышающих 30000, N и K через пробел – количество людей в кругу, и какого по счету указывает считалочка.

Выходные данные

В файл count.out выведите единственное число – номер оставшегося в круге человека

Пример

count.in	count.out
7 3	4

Решение

Как правило, учащиеся решают данную задачу с помощью моделирования с применением массива. Её удобнее решить, если номера мест, в отличие от номеров участников, будут начинаться с 0 и заканчиваться n-1.

Процесс удаления участника из круга моделируется сдвигом всех последующих элементов на место с индексом, на единицу меньшим.

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

#include <iostream>

#define SIZE 30000

int main(){

int n, k, a[SIZE];

std::cin >> n >> k;

n--;

for(int i = 0; i <= n; i++)

   a[i] = i + 1;     //пронумеруем МЕСТА от 0 до n-1

int j = 0;       //место по кругу выбывающего участника

k--;             //на сколько смещаемся позиций при счете

while(n > 0){    //запускать считалочку

   j = (j+k) % (n+1); //кто выбыл? (можно циклом, но долго!!!)

   for(int i = j; i < n; i++)

       a[i] = a[i+1]; //сдвигаем оставшихся

   n--;

}

std::cout << a[0];

}

Задача №191.  Робот  К-79

(Время: 1 сек. Память: 16 Мб)

Московская олимпиада по информатике 2004/05 г. Заочный тур

Петя написал программу движения робота К-79. Программа состоит из следующих команд:

· S — сделать шаг вперед

· L — повернуться на 90 градусов влево

· R — повернуться на 90 градусов вправо

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

Входные данные

Одна строка из заглавных латинских букв S, L, R, описывающая программу для робота. Общее число команд в программе не превышает 200, при этом команд S — не более 100.

Выходные данные

Выведите, сколько шагов будет сделано (то есть выполнено команд S) прежде, чем робот впервые окажется в том месте, через которое он уже проходил. Если такого не произойдет, выведите в выходной файл число –1.

Примеры

№	Ввод	Вывод
1	SSLSLSLSSRSRS	5
2	LSSSS	-1

Решение

Поскольку робот совершает не более 100 перемещений, можно считать, что все эти перемещения в обе стороны ограничены квадратом 200×200. Будем считать начальное положение робота центром этого квадрата (100, 100). В каждый момент времени состояние робота описывается 4 числами – координатами (x, y) и вектором направления {dx, dy}.

#include <iostream>

using namespace std;

int main() {

string s;

cin >> s;

bool here[200][200] = {0,};

int x = 100, y = 100, dx = 1, dy = 0, step = 0;

for(int i = 0; s[i]; i++){

     here[x][y] = true;

     if(s[i]== 'S') {

           x += dx;

           y += dy;

           step++;

           if(here[x][y]){cout << step; return 0;}

     }

     if(s[i] == 'R') {swap(dx, dy); dx = -dx;}

     if(s[i] == 'L') {swap(dx, dy); dy = -dy;}

}

cout << -1;

}

Задача №192.  Часы (acmp.ru)

Петя очень любит наблюдать за электронными часами. Он целыми днями смотрел на часы и считал, сколько раз встречается каждая цифра. Через несколько месяцев он научился по любому промежутку времени говорить, сколько раз на часах за это время встретится каждая цифра, и очень гордился этим.

Вася решил проверить Петю, но он не знает, как это сделать. Вася попросил Вас помочь ему. Напишите программу, решающую эту задачу.

Входные данные

Первая и вторая строки входного содержат начало и конец промежутка времени соответственно. Начальное время не превосходит конечное. Время задается в формате hh:mm:ss (0 ≤ hh < 24, 0 ≤ mm < 60, 0 ≤ ss < 60). hh, mm, ss дополнены ведущими нулями до двух символов. Эти нули также учитываются при подсчете числа цифр.

Выходные данные

Выходной поток должен содержать 10 строк. В i-ой строке должно быть написано, сколько раз встречается цифра i-1.

Пример

№	Ввод	Вывод		№	Ввод	Вывод
1	23:59:58 23:59:59	0 0 2 2 0 4 0 0 1 3		2	13:24:09 13:24:40	5 45 45 45 36 3 3 3 3 4

Решение

Рассмотрим решение данной задачи непосредственным моделированием работы циферблата. Для каждой секунды определим, какие пары цифр на нем отображаются. Для всех пар цифр заведём счётчики (массив dd). Частота появления каждой цифры в таком случае будет легко найдена из этих пар – массива двузначных чисел.

ВАЖНО: Обратите внимание, эта задача, как и многие другие в пособии, которые, казалось бы, предполагают работу со строками, в C++ могут быть решены без строк. Если данные разделяются одним символом, то достаточно после ввода одного значения считывать из потока char (в нашем случае это delimiter), после чего переходить к обработке остальных данных

#include <iostream>

using namespace std;

int main(){

int h1,h2,m1,m2,s1,s2,d[10] = {0,}, dd[60] = {0,};

char delimiter;

cin >> h1 >> delimiter >> m1 >> delimiter >> s1;

cin >> h2 >> delimiter >> m2 >> delimiter >> s2;

while ((h1 < h2) ||

       ((h1 == h2) && ((m1 < m2) ||

       ((m1 == m2) && (s1 <= s2))))){

   dd[h1]++;

   dd[m1]++;

   dd[s1]++;

   s1++;

   if(s1==60) {s1 = 0; m1++;}

   if(m1==60) {m1 = 0; h1++;}

}

for(int i = 0; i < 60; i++){

   d[i/10] += dd[i];

   d[i%10] += dd[i];

}

for(int i = 0; i < 10; i++)

  cout << d[i] << endl;

}

Задача №193.  Бутылки(acmp.ru)

Группа программистов собралась в понедельник и на все свои деньги купила «Sprite» в бутылках емкостью по 0.25 л., не забыв взять сдачу.

Во вторник они сдали пустую посуду, добавили оставшуюся сдачу и вновь купили столько таких же бутылок «Sprite», сколько могли.

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

Требуется написать программу, определяющую минимальную сумму, которой располагали программисты в понедельник.

Входные данные

Входной файл INPUT.TXT состоит из единственной строки, содержащей два целых числа F (стоимость одной бутылки «Sprite») и P (стоимость одной пустой бутылки из-под «Sprite»), разделенных пробелом.

Ограничения: 1 ≤ P < F ≤ 10⁹, начальная сумма не превосходит 2*10⁹.

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число – минимальную сумму, которой располагали программисты в понедельник.

Пример

INPUT.TXT	OUTPUT.TXT
7  3	83

Решение

Обозначим через div деление нацело, через mod – остаток от деления. S_i – сумма, которой располагали программисты в i-ый день. Поскольку они тратили все средства

                                                                             (1)

На следующий день они располагали суммой:

                                                                         (2)

При этом величины F, P, S_i+1нам известны. Если из (1) вычесть (2), то получим

     (3)

Тогда                                                                                (4)

Если учесть, что S_idivFесть количество бутылок, приобретенных программистами в этот день и S_iдолжно быть наименьшим, формула (4) с помощью (2) преобразуется к виду:

                                                        (5)

#include <fstream>

using namespace std;

int main(){

ifstream cin("input.txt");

ofstream cout("output.txt");

int F,P;

cin >> F >> P;

unsigned long long sum = F;

for(int i = 0; i < 4; i++)

   sum += ((sum - F) / P + 1) * (F - P); 

cout <<sum;

}