Конечные автоматы
Однажды известный профессор обнаружил описания k конечных автоматов. По его мнению, нетривиальность конечного автомата, имеющего n состояний и m переходов, можно описать целым числом d = 19m + (n + 239)*(n + 366) / 2 . Чем больше d, тем больший интерес для науки представляет изучение его свойств.
Помогите профессору вычислить нетривиальность имеющихся у него автоматов.
#include <iostream>
using namespace std;
main()
{
int a,b,k,i;
cin>>k;
for(i=1;i<=k;i++)
{
cin>>a>>b;
cout<<(19*b+(a+239)*(a+366)/2)<<endl;
}
}
Алгоритм решения:
Вводим количество конечных автоматов - K. В цикле от 1 до k вводим два числа, вычисляем нетривиальность по заданной в задаче формуле и выводим полученное число.
Нули
Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц.
#include<iostream>
#include<string>
using namespace std;
int main()
{
int b=0,max=0;
string a;
cin>>a; a+='1';
for(int i=0;i<a.size();i++)
{
if(a[i]=='0')b++;
if(a[i]=='1'){
if(max<b)max=b;
b=0;
}
}
cout<<max;
return 0;
}
Алгоритм решения:
Вводим строку нулей и единиц, дописываем в строку последним элементом единицу. Проходим по элементам всю строку, если элемент равен нулю, то увеличиваем счетчик b, затем сравниваем max с b. Если b больше max, то max = b. В конце в переменной b остается максимальное значение, поесть наибольшее количество нулей. После выхода из цикла выводим max.
Число е
Выведите в выходной файл округленное до n знаков после десятичной точки число E. В данной задаче будем считать, что число Е в точности равно 2.7182818284590452353602875.
#include <iostream>
using namespace std;
main()
{
int n,i;
cin>>n;
string s;
s="7182818284590452353602875";
if(n==0) cout<<3;
else
{
cout<<"2.";
for(i=0;i<n-1;i++) cout<<s[i];
if(s[n]>=‘5') cout<<s[n-1]+1-'0';
else cout<<s[n-1];
}
}
Алгоритм решения:
Вводим n количество знаков после запятой. S присваиваем дробную часть числа Е. Если n=0 , выводим 3. Иначе выводим «2.», затем выводим элементы строки до n-1, далее смотрим n-нный элемент, если n>=«5», то округляем в большую сторону s[n-1]+1-‘0’ (перевод символа в int), если нет то выводим s[n-1].
Баскетбол
Известны результаты каждой из 4х четвертей баскетбольной встречи. Нужно определить победителя матча.
#include <iostream>
using namespace std;
int main()
{
int a, b, c, d, e, f, g, h,j,l;
cin >> a >> b >> c >> d >> e >> f >> g >> h;
j = a + c + e + g;
l = b + d + f + h;
if(j ==l)
cout <<"DRAW" << endl;
if(j > l)
cout << 1 << endl;
if(j<l)
cout << 2 << endl;
return 0;
}
Алгоритм решения:
Вводим восемь чисел. В j и l записываем сумму очков команд соответственно и сравниваем эти два числа. При равенстве выводим DRAW, если j>l выводим 1, иначе 2.
Клавиатура
Для данной буквы латинского алфавита нужно вывести справа стоящую букву на стандартной клавиатуре. При этом клавиатура замкнута, т.е. справа от буквы «p» стоит буква «a», от буквы «l» стоит буква «z», а от буквы «m» — буква «q».
#include <iostream>
#include <string>
using namespace std;
int main()
{ int i; char c,x;
string a={'q','w','e','r','t','y','u','i','o','p','a','s','d','f','g','h','j','k','l','z','x','c','v','b','n','m','q'};
cin>>c;
for(i=0;i<=26;i++)
if(a[i]==c) {x=a[i+1];
break;}
cout<<x;
}
Алгоритм решения:
Вводим символ c. В строке а записана последовательность символов клавиатуры, последний символ равен первому, потому что клавиатура кольцевая. Дальше сравниваем введенный символ с символами строки, и после этого выводим a[i+1] символ.
Дом - Школа - Дом
Мальчик Вася каждый день ездит на метро. Утром он едет в школу, а вечером того же дня, обратно из школы, домой. Для того, чтобы немного сэкономить, он покупает электронную смарт-карту на X поездок. Когда он хочет зайти в метро, он прикладывает карту к турникету. Если на карте осталось ненулевое количество поездок, то турникет пропускает Васю и списывает с карты одну поездку. Если же на карте не осталось поездок, то турникет не пропускает Васю, и он (Вася) вынужден купить на этой же станции новую карту на X поездок и вновь пройти через турникет.
Вася заметил, что в связи с тем, что утром метро переполнено, покупать новую карту утром накладно по времени, и он может опоздать в школу. В связи с этим он хочет понять: будет ли такой день, что с утра, поехав в школу, Вася обнаружит у себя на карточке ноль поездок.
Вася больше никуда на метро не ездит и поэтому заходит в метро только на станции около дома и на станции около школы.
#include <iostream>
#include <string>
using namespace std;
main()
{
string a;
int n;
cin>>a;
cin>>n;
if( a=="Home") { if(n%2==0) cout<<"Yes";
else cout<<"Yes";}
if(a=="School") { if(n%2==0) cout<<"No";
else cout<<"Yes";}
}
Алгоритм решения:
Вводим строку и число. Если строка равна «Home» ,то при этом условии у Васи будет день, когда у него утром на карте окажется 0 поездок, значит выводим Yes. Если строка равна School, и количество поездок делится на 2, выводим No, иначе
Yes.
Арбузы
Иван Васильевич пришел на рынок и решил купить два арбуза: один для себя, а другой для тещи. Понятно, что для себя нужно выбрать арбуз потяжелей, а для тещи полегче. Но вот незадача: арбузов слишком много и он не знает как же выбрать самый легкий и самый тяжелый арбуз? Помогите ему!
#include <iostream>
using namespace std;
main()
{
int i,n,max=0,min=30000,a;
cin>>n;
for(i=0;i<n;i++)
{ cin>>a;
if(a>=max) max=a;
if(a<=min) min=a;
}
cout<<min<<' '<<max;
}
Алгоритм решения:
Минимуму присваиваем максимальное значение, максимуму 0. Вводим n количество арбузов, в цикле от 0 до n вводим массу каждого арбуза. Дальше ищем максимальную и минимальную массу и записываем ее в max и min соответственно. После выхода из цикла выводим значения max и min.
