Най-лесно тази задача можем да решим като обходим всички цели числа в интервала [M,N] и за всяко едно от тях проверим дали се дели на 3. Ако това е така, ще го отпечатаме. Това, естествено налага повторение, т. е. организиране на оператор за цикъл. За тази организация е необходимо да отговорим на двата въпроса:
- преминаване към следващото число.
След като уточним, че за инициализация на цикъла е необходимо да дадем начална стойност на i=M, решението на задачата е следната програма:
void main()
{
int i, M, N;
cin>>M>>N;
i=M;
while(i<=N);
{
if (i%3==0) cout<
i++;
}
}
В организацията на цикъла while в тази програма има три основни елемента:
- инициализацията на цикъла:
i=M
- преминаване към следващото число:
i++;
- условието за край:
i<=N.
Тези три елемента са типични за подобен вид задачи. Винаги когато се налага обхождане на предварително зададен интервал, ще се налага тяхното използване. В програмирането се срещат много задачи от този тип. За по-лесното им решаване в езика С++ се използва специален оператор за цикъл for. Синтаксисът му е по-сложен от другите два оператора за цикъл, но организиран чрез него, цикълът е по-компактен и заема най-малко място в текста на програмата.
В него трите основни елемента на цикъла са изнесени извън тялото му и се открояват по-лесно. Ето как изглежда горната програма с използване на цикъл for.
#include
void main()
{
int i, M, N;
cin>>M>>N;
for(i=M;i<=N;i++)
if (i%3==0) cout<
}
Компактността на програмата е очевидна, така че да се заемем с разглеждането на синтаксиса и семантиката на оператора за цикъл for.
-
Синтаксис и семантика на оператора за цикъл for
а) Синтаксис на оператора за цикъл for (правила за запис):
for (израз1; израз2; израз3) оператор;
Където израз1, израз2 и израз 3 са произволни изрази, допустими за езика;
Оператор – произволен прост или съставен оператор;
израз1 - инициализация на цикъла. С него се присвояват началните стойности на параметрите на цикъла;
израз2 - условие за край, управляващо продължителността на цикъла;
израз3 - израз за изменение на текущите стойности на параметрите на цикъла;
оператор – тяло на цикъла;
Досещаме се, че за да бъде безпроблемно изпълнението на цикъла е необходимо израз1, израз2 и израз3 да бъдат свързани помежду си логически: с израз1 се установяват началните стойности на променливите, които участват в условието за проверка, а с израз3 се определят правилата, по които променливите се изменят на всяка итерация на цикъла. Израз1 и израз3 най-често са изрази за присвояване, а израз2 е израз за сравнение. И все пак трябва да отбележим, че според синтаксисът на езика нито един от трите израза не е задължителен, т. е. допустимо е използването и на следния оператор:
for(;;)оператор;
Тъй като в него не е посочено условие за край, той ще се изпълнява безкрайно и тогава в използването му не се вижда особен смисъл.
б) Семантика на оператор for (правила за изпълнение):
При изпълнение на оператор for се поражда следната последователност от действия:
- изчислява се стойността на израз1, която се използва като начална стойност на управляващата променлива на цикъла;
- изчислява се стойността на израз2, която зависи от управляващата променлива;
- ако стойността на израз2 е различна от нула, се изпълнява операторът в тялото на цикъла. След това се изчислява стойността на израз3 и се присвояава нова стойност на управляващата променлива, като управлението се връща в стъпка 2(т.е. изчислява се стойността на израз2), за да се осъществи следващото завъртане на цикъла;
- ако стойността на израз2 е равна на нула, се изпълнява операторът, записан непосредствено след тялото на цикъла.
Условието за проверка – израз2 определя дали операторите в тялото на цикъла ще бъдат изпълнени поне веднъж или ще бъдат прескочени. От механизма на действие на оператор for следва, че израз1 се изпълнява само веднъж. Ако стойността на израз2 е нула още на първото завъртане на цикъла, израз3 изобщо не се изпълнява.
Променливите, които се използват в израз1, израз2 и израз3 трябва предварително да се дефинират според изискването за дефиниране на нови идентификатори, т.е. преди тяхната упореба. Операторът for в С++ позволява деклариране на управляващите структури в самият цикъл.
С
равнявайки двете решения на разглежданата задача можем да формулираме правило, чрез което да замениме оператор while с for и обратно.
-
Задачи за упражнение:
Зад. 1. Посочете колко пъти ще се изпълни тялото на цикъла и какъв ще е резулатата от това, ако:
а) int n=10;
for(int i=1;i<=n;i=i+2) cout<б) int n=5,i;
for(i=1;i<=n;i--) cout<в) int n=-1,i;
for(i=1;i<=n;i--) cout<г) int n=1;
for(int i=1;i<=n;i++) cout<
if (i%3==0) cout<Зад. 2. ДСПК отпечатва на отделни редове n пъти:
а) поздрава ‘Hello’;
б) числата от 1 до n.
Зад. 3. Колко пъти ще се изпълни тялото на цикъла и какъв е резултата от изпълнението на програмния фрагмент?
а) s=0;
for(i=1;i<=3;i++) s+=i;
cout<<”S=”<
б) s=0;
for(i=1;i>=5;i++) s+=i;
cout<<”S=”<в) p=1;
for(i=1;i>=0;i+2) p*=i;
cout<<”P=”<
г) for(i=1,s=0;I<=N;i++, s+=i);
Зад. 4. Запишете следния цикъл for като цикъл while:
int i,s=0;
for(i=1;i<=10;i++) s+=i;
Зад. 5. Да се състави програма, която въвежда цяло положително число n, а след това въвежда още n на брой цели числа и пресмята:
б) произведението им.
Зад. 6. ЛИНИЙКИ
Дадени са две еднакви непрозрачни измервателни линийки с разграфени милиметри. По дължината на всяка линийка са пробити по няколко малки дупки, като дупките са на еднакво разстояние от ръба на линийката. Дупките започват от нулевото деление и след това са разположени равномерно с разстояние между всеки две съседни дупки, равно на М милиметра за едната линийка и на N милиметра за другата. Считаме, че дупки са пробити и на самите крайни деления на линииките, ако там се пада да се пробие дупка, съгласно казаното по-горе. Дължината на всяка от линийките е L милиметра.
Напишете програма LIN.EXE, която въвежда от клавиатурата стойностите на M, N и L, и извежда на екрана броя на дупките, които се виждат след като двете линиики се поставят точно една над друга. Стойностите, които ще се въвеждат са цели положителни числа, като стойностите на M и N са по-малки от 50, а стойността на L може да има най-голяма стойност, равна на 5000.
Пример
Въвеждаме:
1
2
4
Програмата трябва да изведе:
3
Контрол на входните данни
Програмите, които програмистите създават, са предназначени за потребители-неспециалисти по програмиране. Може да се очаква, че в много случаи те биха допускали грешки при въвеждането на необходимите за работата на програмите входни данни. Това може да се случи и не само поради незнание на материята, но и в резултат на най-обикновенна човешка грешка. Ето защо е изключително важна всяка една потребителска програма да бъде написана така, че да може да предвижда всички варианти на грешно въвеждане и да може да дава подходящи съобщения. Това е сложно за програмиране и ще бъде обект на изучаване на други дисциплини на по-късен етап на обучението по програмиране.
Тук ще се опитаме да дадем идея за това как се контролират входните данни при работа с дадена програма. За целта да разгледаме задачата, която използвахме в предходната тема за илюстрация на цикъл for.
Задача: Да се състави програма, която прочита от клавиатурата целите числа M и N и извежда на екрана всички цели числа в интервала [M,N], които се делят на 3.
Решение:
Решението беше описано по горе и окончателния вид на програмата е следния:
#include
void main()
{
int i, M, N;
cin>>M>>N;
for(i=M;i<=N;i++)
if (i%3==0) cout<
}
В тази програма входните данни са стойностите на двете цели променливи M и N, които определят границите на интервала [M, N]. При въвеждането им от потребителя може да се допусне грешката числото M да е по-голямо N, при което интервал практически не съществува. Тогава програмата няма да изведе нищо и потребителят може да остане с впечатление, че тя не работи. Добре е веднага след въвеждането на двете числа, да се направи проверка дали входа е коректен. Това може да стане с оператор if за проверка дали M да е по-малко N по следния начин:
#include
void main()
{
int i, M, N;
cin>>M>>N;
if(M
for(i=M;i<=N;i++)
if (i%3==0) cout<
else
cout<<”въведени са некоректни данни\n”;
}
В този вариант при въвеждане на некоректни входни данни програмата ще спре и няма да продължи своете изпълнение, при това ще изведе съобщение за причината за това свое действие.
Прекратяването на работата на програмата също не е най-добрия вариант за контролиране на действията на потребителя, защото предвижда повторното и стартиране, за да може да бъде изпълнена с коректен вход.
Ще предложим още един вариант за контролиране на входните данни, при който при въвеждане на некоректен вход, потребителят се задължава отново да направи опит за въвеждане и така докато въведе коректни входни данни според изискванията на програмата. Това изисква организация на оператор за цикъл.
Ще изберем оператор за цикъл while, който се организира непосредствено след въвеждане на променливите M и N. Тялото на оператора се изпълнява докато потребителят въвежда некоректни данни, т. е. докато M >= N. При това на всяка изпълнение се извежда съобщение за причината за повторение на въвеждането. Ако още на първото въвеждане данните са коректни, тялото на цикъла не се изпълнява нито веднъж.
cin>>M>>N;
while(M>=N)
{
cout<<”въведени са некоректни данни\nвъведете отново M и N\n”;
cin>>M>>N;
}
Подобни проблеми стоят пред програмистите при решаване на всяка една от задачите. Препоръчваме на читателя да допълва описаните по-нататък програми с проверка за коректен вход. Все пак, както вече споменахме, потребителския интерфейс е обект на изучаване на друга дисциплина, затова с цел да избегнем натоварването на алгоритмите, които ще разглеждаме по-нататък, ние ще се абстрахираме от тези проверки.
Циклични алгоритми
Както вече споменахме една от най-мощните възможности на компютъра е бързото многократно повторение на едно и също действие или изчисление. Ето защо, след като се запознахме и с операторите за цикъл, можем да решаваме много сериозни задачи, които ще разделим на няколко основни групи.
Последователно въвеждане на числа и обработката им
Това са стандартни задачи, при които се осъществява четене на последователност от по едно или няколко числа, като едновременно се обработват за намиране на някакъв резултат.
Задача 1. Отрицателни.
Да се състави програма NEGATIVES.CPP, която въвежда от клавиатурата цели числа до въвеждане на 0 и отпечатва броя на въведените отрицателни числа.
Примерен вход
1
-3
7
-2
-6
0
Примерен изход
3
Решение
-
Ще определим величините, които участват в програмата:
Необходими са ни две целочислени променливи – едната – int a, за да записваме в нея текущо въведеното число и друга – за броя на отрицателните числа. Ще отбележим, че променливата, съдържаща броя на нечетните числа трябва предварително да се нулира: int br=0;
-
Последователното въвеждане на числа е свързано с повторение на определени действия и затова да уточним двете характеристики на повторението:
- Какво се повтаря?
Повтарят се две действия: въвеждане на поредното число и проверка, дали то е отрицателно. В случай, че числото е отрицателно, брояча се увеличава с 1. Тези действия се записват на С++ по следния начин:
cin>>a;
if(a<0)br++;
- До кога се повтаря?
В условието на задачата точно е указан признака за повторение: описаните действия се повтарят, докато въведеното число а е различно от 0.
-
Остава да уточним какъв цикъл ще използваме за реализация на повторенията. Тъй като в условието за край на повторенията участва стойността на променливата а, то е добре тя да получи стойност преди проверката на това условие. От друга страна условието на задачата предполага, че ще трябва да се въведе поне едно число. Ето защо е правилно в случая да използваме операторът do-while.
-
Накрая програмата трябва да изведе броя на отрицателните числа.
Сега можем да напишем текста на програмата:
//negative.cpp
#include
void main()
{
int a,br=0;
do
{
cin>>а;
if(a<0)br++;
}
while(a);
cout<
}
Тази програма вече може да бъде въведена чрез системата за програмиране BorlandС, да бъде съхранена под име NEGATIVES.CPP и да бъде изпълнена.
Допълнителни задачи:
Променете програмата така, че тя да отпечатва броя на числата, кратни на 7.
Какво ще се промени в програмата, ако в условието се изисква да се намери не броя, а сумата на числата, кратни на 7?
Задача 2. Сума К.
Да се състави програма SUMK.CPP, която прочита от клавиатурата цяло число К и след него последователност от числа, докато сумата им стане по-голяма или равна на К, и отпечатва броя на въведените числа.
Примерен вход
10
2
4
5
Примерен изход
3
Решение
-
Необходими величини:
int K; - за първото въведено число
int a; - за текущото число от последователността
int br=0; - за броя на въведените числа. Като всеки брояч, и този трябва да се нулира.
int S=0; - за сумата на числата.
-
Въвежда се променливата K:
cin>>К;
-
Организира се цикъл, в който се повтаря:
cin>>a; //прочита се текущото число
br++; //увеличава се броя на въведените числа,
S+=a; //добавя се прочетеното число към сумата,
докато получената сума не е станала по-голяма или равна на К, т.е. докото S
-
Извежда се броя на въведените числа.
cout<
-
Както и преди, ще използваме цикъл do-while.
Окончателно програмата има следния вид:
//sumk.cpp
#include
void main()
{
int a,br=0,K,S=0;
cin>>K;
do
{
cin>>а;
br++;
S+=a;
}
while(Scout<
}
Допълнителни задачи:
Променете програмата така, че да намира и отпечатва средното аритметично на въведените числа.
Задача 3. Викторина
За училищна викторина трябвало да се съставят отбори от по трима души, но участниците в тях трябвало да се сработват добре, за да има успех всеки отбор. За да се подберат правилно отборите всички участници били анкетирани, като резултатите от анкетата били записани с цели числа [0, 255]. Въпросите от анкетата били зададени така, че от резултата се разбира лесно дали един отбор е добре подбран. А това е така ако сумата от резултатите на тримата участници в отбора е кратна на 3. Да се състави програма ANKETA.CPP, която чете от клавиатурата последователности от три числа (резултатите на тримата участници в отбора) до въвеждане на три нули и отпечатва след всяка от тях – OK, ако отбора е добре сформиран и Error, ако това не е така. За нулевата тройка не се отпечатва нищо
Примерен вход
6 7 8
8 9 3
5 4 12
1 3 5
10 11 4
0 0 0
Примерен изход
OK
ERROR
OK
OK
ERROR
Решение
За да определим дали даден отбор е добре сформиран, е необходимо да намерим сумата от точките на трите участника и да проверим дали се дели на три.
-
Необходими величини:
Тъй като е необходимо на всяка стъпка да обработваме резултатите и на тримата състезатели, ще са ни необходими три целочислени променливи a, b и c за всеки един от състезателите, както и променливата S за сумата от точките на тримата.
int a,b,c, S=0;
-
Още веднага се организира цикъл do-while, в който на всяка стъпка се въвеждат трите числа a,b и c, пресмята се сумата им S и се проверява дали е кратна на 3. Условието за край може да бъде проверено най-лесно, като се вземе под внимание, че сумата на три цели положителни числа (каквито са нашите) е 0 тогава и само тогава, когато и трите са 0.
do
{
cin>>а>>b>>c;
S=a+b+c;
if(s&&s%3)
cout<<”ERROR\n”;//проверката за s се налага от условието, че за последната тройка програмата не отпечатва нищо
else cout<<”NO\n”;
}
while (S);
Тези две стъпки всъщност решават задачата.
В този случай общия вид на програмата е следния:
//anketa.cpp
#include
void main()
{
int a,b,c,S=0;
do
{
cin>>а>>b>>c;
S=a+b+c;
if(S&&S%3) cout<<”ERROR\n”;
else cout<<”OK\n”;
}
while (S);
}
Намиране на оптимален елемент от въвеждана последователност
В темата за оператор за цикъл while решихме задача, в която се въвежда редица от числа и се отпечатва максималното от тях. Този вид задачи са едни от най-популярните в програмирането. Непрекъснато се налага да се намери победител в състезание, да се определи най-висока цена и т.н.
Задача 4. Максимално отрицателно число
Напишете програма MAXNEG.CPP, която въвежда от клавиатурата цели числа, до срещане на числото 0(нула), и извежда на екрана максималното отрицателно число. Ако в последователността не е въведен нито един отрицателен елемент се извежда 0.
Примерен вход
1
-3
7
-2
-6
0
Примерен изход
-2
Решение
Когато се определя оптимален елемент, първата стъпка е да приемем, че един от всички елементи, който отговаря на останалите условия, е евентуален кандидат за оптимален. След това го сравняваме с всички останали и ако намерим такъв, който го превъзхожда – го заместваме. Ще определим величините, които участват в програмата:
-
Необходими са ни две целочислени променливи – едната: int a;, за да записваме в нея текущо въведеното число и друга int mn; – за максималното отрицателно число.
-
Както вече споменахме, първо трябва да открием първото отрицателно число от поредицата и да го обявим за максимално. Да обърнем внимание и на това, че във въвежданата последователност може и да няма отрицателни елементи. Ето защо, трябва да предвидим и варианта да се въведе 0, без да е въведен нито един отрицателен елемент и тогава трябва да отпечатаме 0. Намирането на първия отрицателен елемент ще се реализира с цикъл, в който числата ще се четат от клавиатурата докато бъде въведено отрицателно число или 0.
do cin>>a while(a>0);
-
След като цикълът завърши, се налага да проверим причината за спирането му. Това може да бъде въвеждане на 0, което означава извеждане на 0 и край на програмата. В случай, че е въведено отрицателно число означава, че то трябва да бъде обявено за максимално и въвеждането да продължи до въвеждане на 0, като при това всяко число се проверява дали е отрицателно и дали е по-голямо от определения вече максимален елемент. Ако се открие такова число, то се обявява за максимален елемент. Това се реализира по следния начин:
if(!a) cout<<0<
else
{
mn=a;
while(a)
{
cin>>a;
if(a<0&&a>mn)mn=a;
}
cout<
}
Последният оператор извежда на екрана максималното отрицателно число.
Сега можем да напишем текста на програмата:
//maxneg.cpp
#include
void main()
{
int a,mn;
do cin>>а; while(a>0);
if(!a) cout<<0<
else
{
mn=a;
while(a)
{
cin>>a;
if(a<0&&a>mn)mn=a;
}
cout<
}
}
Допълнителни задачи:
Променете програмата така, че тя да отпечатва минималното въведено положително число.
Какво ще се промени в програмата, ако в условието се изисква да се намери минималното четно число?
Задача 5. Състезание
В състезание по вдигане на тежести при равни резултати на по-предно място се класира по-лекия състезател. Да се състави програма COMP.CPP, която прочита от клавиатурата цяло число n<=50, резултатите и теглата (които могат да бъдат и дробни числа) на n състезатели и отпечатва номера на златния медалист.
Примерен вход
5
150 70
130 65
150 69
120 80
145 100
Примерен изход
3
В тази задача ще трябва да определим оптимален елемент по два признака, като първият е водещ, но при равенство – оптималността се решава в полза на този, с по-добър втори признак (в случая – с по-малко тегло). Ето защо за златния медалист трябва да съхраним не само номера, но и резултата и теглото му.
-
Необходими са ни две целочислени променливи – едната – int n, за броя на състезателите и друга – за номера на златния медалист –int mn. Ще са необходими и по две променливи за постижението и теглото на състезателя, чиито данни въвеждаме в момента – float p,t; както и за постижението и теглото на златния медалист – float mp,mt;
-
Тук за определяне на първоначалната стойност на оптималния елемент, ще използваме факта, че в най-лошия случай резултата на един състезател е 0 и ще приемем този резултат за максимален. Естествено е да очакваме, че при въвеждане на данните за всички състезатели, ще се въведе поне едно постижение, различно от 0 и то ще замести приетото за оптимално нулево постижение. Преди да продължим с въвеждане на данните за броя и постиженията на състезателите, ще направим следната инициализация на променливите, характеризиращи златния медалист:
mp=mt=mn=0;
-
Въвеждаме броя на състезателите:
cin>>n;
-
Сега трябва да въведем последователно постиженията и теглата на всичките n състезатели, като сравним постижението на всеки от тях с най-доброто до момента: Ако е по-добро, да запомним в променливите mn, mt и mp параметрите на този състезател; ако постижението е равно на най-доброто, ще се наложи да сравним теглата на най-добрия и текущия състезател и ако текущия е по-лек, той ще стане най-добър. Във всички останали случаи промени не са необходими. За n-кратното повторение на тези действия ще използваме цикъл for, управляващата променлива, на който ще съдържа във всеки момент номера на текущия състезател.
for(int i=1;i<=n;i++)
{
cin>>p>>t;
if((p>mp)||(p==mp&&t
{
mp=p; mt=t;mn=I;
}
}
-
Накрая извеждаме номера на златния медалист.
cout<Ето окончателния вид на програмата:
//comp.cpp
#include
void main()
{
int n, mn; float p,t,mp,mt ;
mp=mt=mn=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>p>>t;
if((p>mp)||(p==mp&&t
{
mp=p; mt=t;mn=i;
}
}
cout<
}
Отделяне на цифрите на число
Задача 6. Цифри
Напишете програма DIGITS.CPP, която въвежда от клавиатурата цяло, положително число n и извежда на екрана неговите цифри отдясно наляво, като всяка от тях се отпечатва на отделен ред.
Примерен вход
234
Примерен изход
4
3
2
Решение
Лесно можем да определим коя е последната цифра на числото n. За целта е достатъчно да намерим остатъка при деление на n на 10, т.е. n%10. Лесно можем да получим и число, същото като n, но без последната му цифра. Това ще стане като разделим n на 10, т.е n/10. По този начин можем да кажем, че сме задраскали последната цифра на числото.
-
За решението на проблема ще е достатъчна само една целочислена променлива int n; в която ще записваме текущата стойност на числото n.
-
Като начало програмата трябва да въведе числото n от клавиатурата.
cin>>n;
-
След въвеждането ще отпечатваме последователно поредната цифра на числото и ще я “задраскваме” от записа му докато свършат всички цифри, т.е. докато числото стане 0. Това може да се реализира с оператор do-while по следния начин:
do
{
cout<
n/=10;
}
while(n);
Текстът на тази програма изглежда така:
//digits.cpp
#include
void main()
{
int n;
cin>>n;
do
{
cout<
n/=10;
}
while(n);
}
Допълнителни задачи:
Променете програмата така, че тя да отпечатва сумата от цифрите на числото.
Какво ще се промени в програмата, ако в условието се изисква да се намери броя на цифрите на числото?
Задача 7. Обратно число
Да се състави програма REVERT.CPP, която прочита от клавиатурата цяло число n и го отпечатва, като подрежда цифрите му в обратен ред.
Примерен вход
1234
Примерен изход
4321
Решение
Нека да разгледаме числото от конкретния пример. То може да се представи по следния начин:
1234=1*103+2*102+3*10+4=((10*1+2)*10+3)*10+4
По същия начин може да се представи и обратното на това число
4321=((10*4+3)*10+2)*10+1
Лесно се вижда как от първото число може да се получи второто – като се отделят цифрите една по една и се добавят към натрупаното до момента число, умножено по 10. В началото обърнатото число ще има стойност 0 и постепенно цифрите от едното число “ще се прехвърлят” на другото.
-
Необходими са ни две целочислени променливи: едната – int n; за числото и другата int on; - за обърнатото.
-
Като начало да въведем числото n:
cin>>n;
-
След това, докато има цифри в числото n ги прехвърляме в on по следния начин:
on=on*10+n%10;
n/=10;
За да прехвърлим всички цифри е необходимо да организираме цикъл, чието тяло ще съдържа горните два оператора и ще завършва когато свършат цифрите на n, т. е. докато n е различно от 0.
Цикълът ще изглежда по следния начин:
do
{
on=on*10+n%10;
n/=10;
}
while(n);
-
Накрая извеждаме обърнатото число:
cout<Ето окончателния вид на програмата:
// revert.cpp
#include
void main()
{
int n, on=0;
cin>>n;
do
{
on=on*10+n%10;
n/=10;
}
while(n);
cout<
}
Допълнителни задачи:
Eдно число се нарича палиндром ако отляво надясно и отдясно наляво се чете по един и същи начин. Променете програмата така, че да отпечатва “YES”, ако числото е палиндром и ”NO” – в противен случай.
Делимост. Делители. Прости числа.
В много случаи дадена задача се свежда до намиране на делителите на дадено число, проверка дали то е просто или разлагането му на прости делители. Да разгледаме някои типични алгоритми, които решават посочените задачи и да опишем тяхната реализация.
Задача 8. Сума от делителите
Да се състави програма DIV.CPP, която прочита от клавиатурата цяло число n и и отпечатва сумата от тези негови делители, които са различни от 1 и n.
Примерен вход
18
Примерен изход
20
Решение
Числата, които могат да бъдат делители на n са тези, които принадлежат на интервала [2, n/2]. Това е очевидно, защото ако допуснем, че 2 е най-малкият възможен делител, то най-големият се получава като разделим числото на него.
-
Необходими са ни две целочислени променливи: едната – int n; за числото и другата long S=0; - за сумата от делителите му. Числото S е от тип long, за да може в него да се запише сумата от делителите на кое да е число от тип int.
-
Като начало да въведем числото n:
cin>>n;
-
Обхождат се всички евентуални делители и за всеки от тях се проверява дали наистина дели n. Ако това е така, той се добавя към сумата S:
for(int d=2;d<=n/2;d++)
if(n%d==0)S+=d;
-
Накрая се извежда S:
cout<Ето окончателния вид на програмата:
// div.cpp
#include
void main()
{
int n, long S=0;
cin>>n;
for(int d=2;d<=n/2;d++)
if(n%d==0)S+=d;
cout<
}
Задача 9. Просто число
Да се състави програма PRIME.CPP, която прочита от клавиатурата цяло число n и отпечатва “PRIME”, ако числото е просто и “NOPRIME” в противен случай..
Примерен вход
7
Примерен изход
PRIME
Примерен вход
14
Примерен изход
NOPRIME
Решение
Решението на тази задача може лесно да се изведе от предходната, тъй като е очевидно, че едно число е просто, ако сумата от делителите му е 0. Тогава единственото, което трябва да се промени в предходната задача е операторът за отпечатване и така решението ще изглежда по следния начин:
#include
void main()
{
int n, S=0;
cin>>n;
for(int d=2;d<=n/2;d++)
if(n%d==0)S+=d;
if(S) cout<<”NOPRIME\n”;
else cout<<”PRIME\n”
}
Ако разгледаме внимателно изпълнението на тази програма, ще установим, че цикълът for се изпълнява за всички стойности на d в интервала [2, n/2], независимо от това, че е ако то не е просто, това няма смисъл. Това е крайно нерационално и навежда на мисълта изпълнението на цикъла да се прекратява веднага след срещането на първия делител на числото n. Това може да се постигне, като се добави оператор break, след проверката за делимост. Тогава окончателният вид на програмата е следния:
// prime.cpp
#include
void main()
{
int n, S=0;
cin>>n;
for(int d=2;d<=n/2;d++)
if(n%d==0){S+=d;break;}
if(S) cout<<”NOPRIME\n”;
else cout<<”PRIME\n”;
}
Задача 10. Най-голям общ делител
Да се състави програма NOD.CPP, която прочита от клавиатурата две цели числа M и N и отпечатва техният най-голям общ делител. Ако двете числа са взаимно прости отпечатва 1.
Примерен вход
18 42
Примерен изход
6
Решение
За да решим тази задача ще използваме известния в математиката Алгоритъм на Евклид за намиране на най-голям общ делител на две числа:
-
Ако М=N, техният общ делител е едно от двете числа.
-
Докато двете числа са различни се изпълнява следното:
Ако M -
Когато двете числа се изравнят – резултатът е техния НОД.
Тук можем веднага да напишем пълния текст на прогрмата:
//nod.cpp
#include
void main()
{
int M,N;
cin>>M>>N;
while(M !=N)
if(M
else M-=N;
cout<
}
Задача 11. Прости делители
Да се състави програма DIVPR.CPP, която прочита от клавиатурата цяло число n и отпечатва всички негови прости делители, взети с тяхната кратност.
Примерен вход
24
Примерен изход
2 – 3
3 – 1
Решение
Прости делители на n могат да бъдат числа, които принадлежат на интервала [2, n/2]. Ако всеки път, когато намерим делител на n, извършваме делението толкова пъти, колкото е възможно и чак тогава преминаваме към следващото число, можем да гарантираме, че винаги ще попадаме на прости делители. Като добавим и брояч, който всеки път отчита колко пъти сме разделили оставащото число на делителя, ще можем да отпечатаме и неговата кратност. Този алгоритъм се реализира по следния начин:
-
Необходими са целочислени променливи за числото n, за текущия възможен делител d, както и за неговата кратност к.
int n,d,k=0;
-
Първо се прочита числото:
cin>>n;
-
Обхождат се последователно всички възможни делители, като за всяко d се проверява дали n се дели на него. Ако се дели, се извършва делението и се увеличава с 1 кратността на текущия делител. Ако числото d не дели n и отчетената до момента кратност е различна от 0, на екрана се извежда d и тази кратност, след което кратността се нулира. Щом d не дели n, във всички случаи се преминава към следващото число.
for(d=2;d<=n/2;)
if(n%d==0){k++;n/=d;}
else
{
if(k){ cout<
d++;
}
Окончателно програмата има следния вид:
//divpr.cpp
#include
void main()
{
int n,d,k=0;
cin>>n;
for(d=2;d<=n/2;)
if(n%d==0){k++;n/=d;}
else
{
if(k){ cout<
d++;
}
cout<
}
Вложени цикли
Вече стана въпрос, че в тялото на който и да е от операторите за цикъл може да участват произволни оператори. В това число и оператори за цикъл. Тогава, подобно на оператора if, ще казваме, че имаме вложени оператори за цикъл. Когато се влагат два оператора за цикъл, при изпълнението им трябва да се има предвид, че на всяка итерация на външния цикъл съответства пълно завъртане на вътрешния. Да разгледаме една примерна задача, която изисква влагане на цикли:
Задача 12. Монети
В една държава разполагат с монети от 2 и 5 пари. Да се състави програма Moneti.cpp, която по въведена сума S отпечатва всички възможни комбинации от монети, с които тя може да се представи. Ако тя не може да се представи с тези монети, отпечатва “NO”.
Примерен вход
17
Примерен изход
1.2+3.5
6.2+1.5
Примерен вход
3
Примерен изход
NO
Решение
За решаването на задачата ще разгледаме всички възможни комбинации от монети от по 2 и 5 пари и ако сумата от тези монети е S, ще ги отпечатваме. Това ще реализираме с два цикъла for, единият от които обхождa всички възможности за монети от по 2 пари, а втория за всяка такава възможност обхожда всички възможности от по 5 пари..
-
Ще са ни необходими 3 целочислени променливи: едната за сумата – int S;, а другите две съответно за отчитане броя на монетите от 2 и 5 пари – int i2, i5;.
-
Като начало програмата трябва да въведе сумата S от клавиатурата:
cin>>S;
-
Ето как ще организираме двата цикъла, за които стана дума:
-
първият цикъл ще се отнася за броя монети от по 2 пари, с които би могла да бъде образувана сумата. Те могат да бъдат най-малко 0 и най-много S/2. Ето защо, управляващата променлива на първия цикъл for ще се мени от 0 до S/2, обхождайки всички числа:
for(i2=0;i2<=S/2;i2++)
-
в тялото на първия цикъл ще вложим втория, чиято цел ще бъде да обходи всички възможни броеве монети от по 5 пари и подобно на първия, тези броеве ще са в интервала от 0 до S/5.
for(i5=0;i5<=S/5;i5++)
На всяка стъпка на вторият цикъл трябва да проверяваме дали сумата от стойностите на текущите за момента броеве монети е равна на s и ако е така – да ги отпечатаме
if(i2*2+i5*5==S) cout< -
Накрая трябва да предвидим и възможността сумата S да не може да се получи от наличните монети, тогава нашата програма трябва да отпечата “NO”. За да успеем да проверим тази ситуация, ще използваме допълнителна променлива int b; която ще има стойност 0, ако с нито една комбинация от брой монети не се получава сумата S и различна от 0, ако поне една комбинация от брой монети е удовлетворила сумата. Ето защо при всеки печеливш случай ще увеличаваме b с 1. В края на програмата трябва да проверим стойността на b и ако все още е 0, да изведем “NO”
Текстът на тази програма изглежда така:
//moneti.cpp
#include
void main()
{
int i2,i5,s,b=0;
cin>>s;
for(i2=0;i2<=s/2;i2++)
for(i5=0;i5<=s/5;i5++)
{
if(i2*2+i5*5) cout<
b++;
}
if(!b)cout<<”NO\n”;
}
Допълнителни задачи:
С помощта на прозореца за проследяване на програми проследете как се променят стойностите на величините в програмата в зависимост от изпълняваните оператори.
Изпълнете файла MONETI.ЕХЕ с посоченият пример и проверете дали програмата ви връща правилен отговор. Проверете я и с още тестови примери.
Променете програмата така, че да отпечатва това представяне на сумата, което има най-малко монети. Какво ще се промени, ако условието изисква сумата да бъде представена с възможно най-голям брой монети?
Задача 13. Представяне на число
Да се състави програма SUM2.CPP, която прочита от клавиатурата цяло число n и отпечатва всички негови представяния като сума от три различни числа.
Примерен вход
10
Примерен изход
1+2+7
1+3+6
1+4+5
2+3+5
Решение
За да решим задачата е необходимо да разгледаме всички възможни стойности за всяко едно от трите числа и да отпечатаме само тези тройки, чиято сума е n.
-
Необходими са ни следните променливи – int n; - за числото, което ще въведем от клавиатурата и ще представим като сума от три числа; три целочислени променливи int a,b,c;, образуващи сумата от трите числа.
-
Като начало да въведем числото n:
cin>>n;
-
Числото a може да бъде измежду числата от 1 до n/3, защото ако , то и и a+b+c>n. Ето защо, ще се наложи да обходим всички възможни стойности за a, което е най-удачно да стане с цикъл for:
for(a=1;a<=n/3;a++)
-
За всяка стойност на а е необходимо да обходим оставащите възможни стойности на b. Числата a и b трябва да са различни, а и се налага да избегнем повторното отпечатване на дадена сума. (например ако вече сме отпечатали 2+4+5, не трябва да отпечатваме 4+2+5, защото това е същата сума). Затова ще започваме обхождането на евентуалните стойности за b от a+1. Променливата b може да заема стойности не по големи от n-a+1. Ето защо цикълът, който ще обхожда евентуалните стойности на b ще има следния вид:
for(b=a+1;bНа всяка стъпка в този цикъл ще трябва да изчисляваме стойността на третата променлива с по следния начин:
c=n-a-b;
-
Получената тройка числа ще отпечатаме само в случай, че c>a и c>b, за да избегнем повторението на някои представяния.
Двата вложени цикъла ще изглеждат по следния начин:
for(a=1;a<=n-3;a++)
for(b=a+1;b
{
c=n-a-b;
if(c>a&&c>b) cout<
}
Ето окончателния вид на програмата:
// sum3.cpp
#include
void main()
{
int n,a,b,c;
cin>>n;
for(a=1;a<=n-3;a++)
for(b=a+1;b<(n-a)/2;b++)
{
c=n-a-b;
if(c>a&&c>b) cout<
}
}
Допълнителни задачи:
С помощта на прозореца за проследяване на програми проследете как се променят стойностите на величините в програмата, в зависимост от изпълняваните оператори.
Изпълнете файла SUM3.ЕХЕ с посоченият пример и проверете дали програмата ви връща правилен отговор. Проверете я с още тестови примери.
Задачи за упражнение:
Зад. 1 Да се състави програма SUMMULT.cpp, която чете от клавиатурата последователност от цели числа, до въвеждане на 0 и отпечатва сумата на четните и произведението на нечетните от въведените числа.
Примерен вход:
1
2
3
4
5
6
0
Примерен изход:
12 15
Зад. 2. Да се състави програма SUMK.CPP, която прочита от клавиатурата цяло число К и след него последователност от числа, докато броят им стане равен на К, и отпечатва броя на въведените числа, кратни на 5.
Примерен вход
4
2
4
5
1
Примерен изход
1
Зад. 3. Да се състави програма TWONEG.CPP, която чете от клавиатурата последователност от числа докато не се въведат две отрицателни и отпечатва броя на всички числа, с последна цифра 5.
Примерен вход
10
-2
45
15
1
-3
Примерен изход
2
Зад. 4. Щастливи дати
Една рожденна дата е щастлива когато сумата от цифрите на деня, месеца и годината на раждане е число, което при четене от дясно наляво и от лява надясно е едно и също. Да се състави програма DATE.CPP, която чете от клавиатурата тройки числа d,m и g, съдържащи съответно деня, месеца и годината на раждане. Въвеждането спира когато се въведе дата 00.00.0000. В края програмата отпечатва броя на щастливите рожденни дати.
Примерен вход:
26 12 1959
17 07 1784
23 02 2000
10 01 1982
15 03 1995
23 01 1980
11 01 1421
00 00 0000
Примерен изход
4
Зад. 5. Да се състави програма THREE.CPP, която чете от клавиатурата последователност от тройки реални числа до въвеждане на такава тройка, елементите на която не могат да бъдат страни на триъгълник, и отпечатва броя на тези тройки, чиито елементи са страни на равностранен, равнобедрен и разностранен триъгълник.
Примерен вход
10 4 7
2 3 4
40 45 38
5 5 5
7 7 7
8 8 9
9 8 9
1 9 2
Примерен изход
2 2 3
Зад. 6. Да се състави програма SEC7.CPP, която чете от клавиатурата редици от по пет числа, до въвеждане на строго растяща редица, и отпечатва на екрана сумата от елементите на последната редица.
Примерен вход
10 4 7 3 6
2 3 4 58 6
40 45 38 33
5 5 5 2 3
70 70 70 70 70
1 2 3 4 5
Примерен изход
15
Зад. 7. Да се състави програма TWONEG1.CPP, която чете от клавиатурата последователност от числа докато не се въведат две отрицателни и отпечатва минималното от всички въведени числа, с последна цифра 5.
Примерен вход
10
-2
45
15
1
-3
Примерен изход
15
Зад. 8. Да се състави програма SUMK1.CPP, която прочита от клавиатурата цяло число K и след него последователност от числа докато броят им стане равен на K и отпечатва най-голямото от въведените числа, кратни на 5.
Примерен вход
10
2
4
5
7
15
3
5
18
20
1
Примерен изход
20
Зад. 9. Да се състави програма PTREE.CPP, която чете от клавиатурата последователност от тройки реални числа до въвеждане на такава тройка, елементите на която не могат да бъдат страни на триъгълник и отпечатва номера на триъгълника с най-голям периметър.
Примерен вход
10 4 7
2 3 4
40 45 38
5 5 5
7 7 7
8 8 9
9 8 9
1 9 2
Примерен изход
3
Зад. 10. Да се състави програма SEC.CPP, която чете от клавиатурата редици от числа от по пет елемента, до въвеждане на строго растяща редица, и отпечатва на екрана най-голямата сума от елементи на редица.
Примерен вход
10 4 7 3 6
2 3 4 58 6
40 45 38 33
5 5 5 2 3
70 70 70 70 70
3 4 5 6 7
Примерен изход
350
Зад. 11. Да номерираме позициите на цифрите на числото отдясно наляво, започвайки от 1. Тогава първата цифра на числото 234 е 4, втората - 3, а третата - 2. Да се състави програма EVENDIG.CPP, която прочита от клавиатурата цяло число n и отпечатва сумата на тези от цифрите му, които са на четни позиции.
Примерен вход
1234
Примерен изход
4
Зад. 12. При условията на предната задача, да се състави програма ODDDIG.CPP, която прочита от клавиатурата цяло число n и отпечатва произведението на тези от цифрите му, които са на нечетни позиции.
Примерен вход
3456
Примерен изход
24
Зад. 13. Да се състави програма DIGIT1.CPP, която чете от клавиатурата цяло число n и отпечатва “YES”, ако като се задраска първата му цифра от ляво надясно се получава число, кратно на 3 и ”NO” в противен случай.
Примерен вход
12346
Примерен изход
YES
Примерен вход
12345
Примерен изход
NO
Зад. 14. Да се състави програма DIGIT2.CPP, която прочита от клавиатурата цяло число n и цяло число k (1<к<5) и отпечатва числото, получено като премахнем k-тата цифра на n от лявo надясно.
Примерен вход
4567 2
Примерен изход
467
Зад. 15. Да се състави програма DIGIT3.CPP, която прочита от клавиатурата цяло число n и цяло число k (1<k<5) и отпечатва квадрата на числото, получено като задраскаме k-тата цифра на n от дясно наляво.
Сподели с приятели: