Задача за програмиране 10 Програмно осигуряване на съвремените компютри (обобщение) 13 Системи за програмиране 15

Примерен вход

2116

• 
  Събира първата цифра на първото число с последната цифра на второто число. Ако резултатът е двуцифрено число, цифрите му се събират. Получената цифра се записва като най-лява за числото.
  
• 
  Втората цифра се получава като по същият начин се обработят втората цифра на първото число и предпоследната цифра на второто число и т. н.
  
• 
  След сумирането на последната цифра на първото число и първата цифра на второто по посочената схема, се получава последната цифра на новото число.
  

Гошо е много добър програмист, но е затрупан от поръчки, затова възлага на вас написването на програмата за получаване на кода.

Програмата се нарича KASA.EXE и получава от клавиатурата две цели числа с равен брой цифри, след което извежда на екрана получения по горната схема код.

Примерен вход

492971 851673

1710016

14

Примерен изход

1 2 3

Примерен вход

15

Примерен изход

NO

Зад. 18. За всеки правоъгълен триъгълник е в сила равенството a²+b²= c² / Теорема на Питагор/, където a и b са катетите, а c е хипотенузата на триъгълника. Да се състави програма PITAGOR.CPP, която за дадено естествено число N намира и отпечатва всички тройки естествени числа a, b и c, не по-големи от N, които могат да бъдат страни на правоъгълен триъгълник.

Примерен вход

11

Примерен изход

3 4 5

6 8 10

5

Примерен изход

2 3 4

2 4 5

3 5 2 18

0 4 2

3 5 1

3

Примерен изход

6

Зад. 22. Да се състави програма DIGDIF.CPP, която въвежда от клавиатурата цяло число N и намира броя на всички трицифрени числа по-малки от N, които не съдържат еднакви цифри.

Примерен вход

120

9

Примерен вход

12

Примерен изход

0

Зад. 23. Група от N деца отива на почивка. В почивната станция разполагат със стаи с по 3 и 4 легла. Да се състави програма CHILDREN.CPP, която въвежда от клавиатурата броя на децата N и отпечатва броя на различните разпределения на децата по стаите. Ако такова разпределение е невъзможно, на екрана се извежда “NO”.

30

Примерен изход

3

Задачи от състезания:

Зад. 24 АВТОПАРК. Група разузнавачи трябвало да проучат състоянието на автопарка на противника. За целта те проникнали в базата и установили, че противниците притежават леки автомобили (с по 4 колела), товарни автомобили (с по 6 колела) и мотори с кош (с по 3 колела). Те внимателно преброили превозните средства и установили, че общият брой колела е N, след което ги описали. За съжаление при изтеглянето, разузнавачите попаднали на засада и се наложило да прекосят река, при което част от документацията се намокрила и се загубила важна информация. Когато прегледали останалата информация, установили, че се чете ясно само броят на колелата. За да възстановят информацията се наложило да се напише програма, която намира всички различни комбинации на трите вида превозни средства за определения брой колела. Тъй като програмистът на групата бил много болен (много силно настинал при преминаването на реката) се налага вие да им помогнете като напишете програма CARS.EXE, която прочита от клавиатурата цялото число N (3 < N < 50) и отпечатва на отделни редове на екрана различните комбинации на превозните средства, като ги подрежда на първо място броя на леките автомобили, на второ – броя на товарните автомобили и на трето – броя на моторите с кош.

Примери:

Вход Вход

10 16

1 0 2 1 0 4

1 1 0 1 2 0

1 1 2

Задачата е подобна на задачата с монетите, решена по-горе. За нейното решение е необходимо да се организират три вложени оператора for, които ще обхождат съответните възможности за брой коли, брой товарни автомобили и брой мотори с кош, като на всяка стъпка на най-вътрешния цикъл проверяваме дали текущата комбинация е възможна и ако е, я отпечатваме. Програмата има следния вид:

//cars.cpp

#include

{

int i,j,k,N;

for(i=0;i<=N/4;i++) //този цикъл обхожда възможния брой леки автомобили

for(j=0;j<=N/6;j++) //този цикъл обхожда възможния брой товарни автомобили

for(k=0;k<=N/3;k++) //този цикъл обхожда възможния брой мотоциклети с кош

if(i*4+j*6+k*3==N)

cout<

}
Лабораторен практикум №4

Циклични алгоритми

Зад. 1. Въведете следната програма:

#include

{

int a; int S=0;

{

cout<<”vyvedi 4islo:”; cin>>a;

}

while(a!=0);

cout<<“sumata ot vyvedenite 4isla e:”<

}

• 
  Тествайте програмата със следните входни данни:
  

2345, 12345, 3456, 3456, 4567, 5678, 890, 567, 0

1, 2, 3, 4, 5, 6, 7, -7, -6, -5, -4, -3, -2, -1, 0

• 
  Има ли тестове, които връщат некоректен отговор?
  
• 
  Коригирайте програмата така, че да работи коректно. Опишете какви са корекциите.
  

Тествайте програмата при следните входни данни:

2, 8, 6, 8, 22, 67, 234, 345, 5, 6, 2, 8, 6, 8, 22, 67, 234, 345, 5, 6, 2, 8, 6, 8, 22, 67, 234, 345, 5, 6, 2, 8, 6, 8, 22, 67, 234, 345, 5, 6,0

2345, 12345, 3456, 3456, 4567, 5678, 890, 567, 0

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0
Променете програмата така, че да може да преброява и числата, кратни на 3 и да отпечатва този брой.

Напишете текста на новата програма.

Тествайте програмата при следните входни данни:

2, 8, 6, 8, 22, 67, -234, -345, 5, -6, -2, -8, 6, 8, -22, 7, -234, -45, -6, - 8, 22, 67, 234, 345, 5, 6, 2, 8, 6, 8, 22, 67, 234, 345, 5, 6,0

2345, 12345, 3456, 3456, 4567, 5678, 890, 567, 0

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0

Какво трябва да се промени в програмата, че да може да отпечатва максималното положително число?

Напишете текста на новата програма.

Зад. 4. Да се състави програма, която въвежда от клавиатурата последователност от точки в равнината, зададени със своите координати и отпечатва координатите на тази от тях, която е най-близо до центъра на координатната система.

Тествайте програмата при следните входни данни:

2 3

3 4

6. 
   7.8
   

6. 
   3.5
   
7. 
   5.8
   
8. 
   6.9
   

Коригирайте програмата така, че да отпечатва и броя на точките от І, ІІ, ІІІ и ІV квадрант. Напишете текста на новата програма.

Тествайте програмата при следните входни данни:

1. 
   15
   

11. 
    135
    

123. 
     3456
     
124. 
     5678
     

#include

long int n,k,Sum=0;

void main()

{ cout<<"Въведете числото n= "; cin>>n;

Sum+=n%10; k=n/10;

do

{

Sum+=k%10;

}

while(k!=0);

}
a) Тествайте програмата за следните входни данни:

1234; 4321; 343; 132112; 5113; 2147483647;

и запишете получените резултати.

б) Коригирайте програмата така, че вместо с do-while да работи само с while -цикъл.

в) Допълнете програмата така, че да отпечатва само онези въведени числа, на които сумата от цифрите съвпада с произведението им. Напишете текста на новата програма.

Зад.2. Да се състави програма, която въвежда положително цяло число и намира, и отпечатва неговото огледално (обърнато).

а) Тествайте програмата за следните входни данни:

123; 4321; 12345; 1234567891; 1234567893;

и запишете получените резултати. Ако се налага коментирайте някои от резултатите.

б) Променете програмата така, че при въведено число да създава ново,съдържащо двойно повече цифри, и което се получава като към старото се залепи неговото обърнато. Напишете текста на новата програма и я тествайте със същите числа.

Зад.3. Да се състави програма, която въвежда две цели числа и отпечатва техният най-голям общ делител.

а) Тествайте програмата за следните двойки входни данни:

(45,137); (45,566); (128,-4192)

и запишете получените резултати.

Зад.4. Да се състави програма, която въвежда цяло положително число и определя дали е просто.

а) Проверете и запишете, кои от следните няколко числа са прости:

137; 537; 1129; 3715; 4293; 4297; 3421

б) Допълнете програмата така, че за останалите числа (които не са прости) да отпечатва първият открит делител. Напишете текста на новата програма.

Функции

1. 
   Теоретични бележки
   

1. 
   Пример
   

Задача: Да се състави програма COUNTEVEN.CPP, която въвежда от клавиатурата числа до въвеждане на 0 и отпечатва броя на въведените четни числа.

Решение:

Такава задача вече сме решавали и тук можем да разгледаме направо програмата, която я реализира:

//counteven.cpp

#include

void main()

{

int a,b=0;

do

{

cin>>а;

if(a&&a%2==0)b++;

}

while(a);

cout<

}
Тук е добре да обърнем внимание на проверката за това дали дадено число е четно. Тази проверка се извършва сравнително лесно в термините на езика С++, но понякога има условия, проверката на които не е толкова тривиална. Дори има случаи, при които кодът, който трябва да се напише за да се извърши дадена проверка е по-голям и по-сложен от останалата част от програмата. В момента целта не е да разглеждаме толкова сериозни примери и затова ще се спрем на една сравнително по-лека задача:

Задача: Да се състави програма COUNTPRIME.CPP, която въвежда от клавиатурата естествени числа до въвеждане на 0 и отпечатва броя на въведените прости числа.

Решение:

Тук е ясно, че единственото, което различава тази задача от предходната е проверката за това дали числото е просто, докато в предишната се проверява дали то е четно. За да се ориентираме как ще изглежда главната функция, на мястото на проверката ще напишем текст на български:

//countprime.cpp

#include

void main()

{

int a,b=0;

do

{

cin>>а;

if(а е просто число)b++;

}

while(a);

cout<

}

Вече разглеждахме задачата за определяне на това дали дадено число е просто и знаем, че за решението и е необходимо да организираме цикъл, който обхожда всички възможни делители на числото и ако намери негов делител, установява, че числото не е просто, а в противен случай – е просто. Това би усложнило написаната по-горе програма. Ясно е, че ако можем да изнесем проверката извън нея, задачата ще се улесни значително. Ето защо ще използваме предоставения от езика С++ механизъм за дефиниране на потребителски функции и ще опишем функция, която ще получава като параметър цяло число х и ще връща стойност 1, ако числото е просто и стойност 0, ако не е. Функцията ще изглежда по следния начин:

int prime(int x)

{

if(x==0||x==1) return 0; //нулата не е просто число

for(int d=2; d<=sqrt(x);d++)

if(x%d==0)return 0;

return 1;

}

След като сме написали тази функция, можем да я използваме в нашата програма, като я извикаме на мястото, където на български сме написали “а е просто число”. Тогава функцията main вече ще има следния вид:

void main()

{

int a,b=0;

do

{

cin>>а;

if(prime(a))b++;

}

while(a);

cout<

}

Накрая ще отбележим, че за да се изпълни коректно програмата, е необходимо да включим библиотеката math.h, заради функцията sqrt.

Използването на функциите в програмите на С++ е толкова често явление, че реално една програма представлява списък от използваните в нея функции. Да разгледаме основните синтактични изисквания при описание и обръщение към функция.

2. 
   Описание и използване на функции
   

а) Синтаксис на описание на функция

тип име_на_функцията(списък_от_формални_параметри){тяло_на_функцията }

тип – задава се типа на резултата, който функцията връща. Ако не се налага функцията да връща резултат, като тип се задава void.

име_на_функция – произволен идентификатор

списък_от_формални_параметри – задават се параметрите, използвани за описание на функцията, като за всеки параметър се посочва неговия тип и различните параметри се отделят един от друг със запетая.

Списъкът от формални параметри има следния синтаксис:

списък_от_формални_параметри::=тип идентификатор, тип идентификатор ...

тяло_на_функцията – тук се описват всички локални за функцията обекти и операторите, които трябва да се изпълнят в нея. Реда на описание на обектите и операторите няма значение, но не се допуска използването на даден обект, преди той да е дефиниран. Ако е посочена стойност, която функцията трябва да върне, в тялото и задължително трябва да фигурира поне един оператор return.
Забележка: Една функция може да няма параметри, но скобите, които ги заграждат, са задължителни.

б) Семантика на описание на функция:

Както вече споменахме по-горе, функцията е основната структурна единица на С++ програмата. Описанието на всяка от функциите се приема от компилатора информативно. Самото изпълнение на функцията се реализира след обръщение към нея в някоя от другите функции или дори в собственото и тяло.

в) Обръщение към функция:
Синтаксис(правила за запис):

име_на_функция(списък_от_фактически_параметри)

Семантика(правила за изпълнение):

В момента на обръщение към функцията за всеки параметър се заделя памет и в нея се копира стойността на фактическите параметри, с които е извикана функцията. Започва реалното изпълнение на функцията с копираната вече стойност. Когато това изпълнение приключи, паметта заемана от нейния параметър се освобождава, а самата функция връща на мястото, от което е извикана, получената стойност.

Пример 1:

Нека да разгледаме функцията prime, описана по-горе. При описанието и е използван целочисления формален параметър х. Този параметър се използва за описанието на тялото на функцията. Самото описание предвижда обработка на параметъра х. При обръщението към функцията обаче, е използван фактическият параметър а, т. е. променливата от функцията main, за която трябва да бъде проверено дали е просто число или не.

Забележка: Обръщението към функцията може да се използва като оператор, или ако функцията връща резултат от някакъв тип – навсякъде, където се допуска използването на величина от този тип. Фактическите параметри са реалните стойности, с които се изпълнява функцията.

г) Формални и фактически параметри:

• 
  формални параметри: използват се само при описанието на функция, като при това се указва точно техният тип. При описанието на функцията формалните параметри се отделят един от друг със запетая.
  
• 
  фактически парамерти: използват се при обръщението към функцията. В качеството на фактически параметри могат да се използват произволни изрази. Фактическите параметри съответстват по брой и по тип на формалните, така че при извикване техните стойности да бъдат точно копирани на заделените места в оперативната памет на компютъра.
  

д) Оператор return:
Синтаксис(правила за запис):

return израз;

израз – това е произволен израз, който трябва да съответства по тип на типа, който връща функцията по дефиниция.

Семантика(правила за изпълнение):

Когато при изпълнението на функцията се достигне до изпълнение на оператора return, първо се изчислява изразът, записан след думата return, след което изпълнението на функцията се прекратява. Цялата заемана от нея памет се освобождава и изчислената вече стойност се връща на мястото, от което е била извикана функцията.

е) място на функцията в програмата:

Както вече отбелязахме в темата “Структура на програма на С++”, функцията е основната структурна единица в програмата. В една програма винаги трябва да има главна функция. Реда на описание на функциите няма значение, но единственото изискване е да няма обръщение към функция, която не е била дефинирана до този момент. Понякога това изискване създава проблеми при подреждането на функциите. Ето защо в езика С++ е предвидена възможност да се декларират всички функции в програмата посредством прототипи. Те позволяват обръщение към дадената функция навсякъде, независимо от мястото където е описана. Обикновенно прототипите се описват в началото на програмата. Те имат следния синтаксис

Прототип

тип_на_функция име_на_функция (параметри_на_функция );

След всичко, казано за функции ще представим общият вид на разглежданата програма.

//countprime.cpp

#include

int prime(int x)

{

if(x==0||x==1) return 0; //нулата не е просто число

for(int d=2; d<=sqrt(x);d++)

if(x%d==0)return 0;

return 1;

}

void main()

{

int a,b=0;

do

{

cin>>а;

if(prime(a))b++;

}

while(a);

cout<

}

При този запис на програмата функцията prime трябва задължително да е дефинирана преди main, която се обръща към нея. Ако не искаме да се съобразяваме с това, е достатъчно да опишем нейния прототип в началото на програмата. Ето как би изглеждала тя в този случай:

//countprime.cpp

#include

int prime(int x);

void main()

{

int a,b=0;

do

{

cin>>а;

if(prime(a))b++;

}

while(a);

cout<

}

int prime(int x)

{

if(x==0||x==1) return 0; //нулата не е просто число

for(int d=2; d<=sqrt(x);d++)

if(x%d==0)return 0;

return 1;

}

2. 
   Решени задачи
   

Задача 1. Палиндроми.

Да се състави програма PALINDROM.EXE, която въвежда от клавиатурата две числа m и n и извежда всички палиндроми в интервала [m, n]

Примерен вход

110 150

Примерен изход

111

121

131

141

Решение

Вече сме разглеждали задачата за проверка на хипотезата дали едно число е палиндром. Използвахме следния подход: намираме обратното на числото и го сравняваме с него. Ако двете числа са равни, това означава, че нашето число е палиндром, в противен случай – не е. След като идеята е ясна, лесно можем да напишем функция, която приема като параметър цяло число х, и връща като резултат 1, ако числото е палиндром и 0 – ако не е. Това предполага, че типа на връщания от функцията резултат е int. Ето как ще изглежда описанието на функцията palindrom:

int palindrom(int x)

{

int ox=0, a=x ;

while(x)

{

ox=10*ox+x%10 ;

x/=10 ;

}

return (a==ox) ;

}

Като използваме описаната функция можем да открием палиндромите в зададения интервал като с помощта на цикъл for обходим всяко цяло число в този интервал и чрез обръщение към функцията проверяваме дали числото е палиндром. Ако функцията върне стойност 1 за някое число, то трябва да се отпечата. По този начин главната функция има следния вид:

void main()

{

int m,n;

cin>>m>>n ;

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

if(palindrom(i))cout<}

За да получим цялата програма е достатъчно да включим входно изходната библиотека iostream.h в началото, преди описанието на функцията palindrom.

Ето окончателния вид на програмата:

//palindrom.cpp

#include

int palindrom(int x)

{

int ox=0, a=x ;

while(x)

{

ox=10*ox+x%10 ;

x/=10 ;

}

return (a==ox) ;

}

void main()

{

int m,n;

cin>>m>>n ;

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

if(palindrom(i))cout<}
Задача 2. Най-голям общ делител.

Да се състави програма NOD.EXE, която въвежда от клавиатурата три цели числа m, n и к и извежда всички двойки числа в интервала [m, n], които имат най-голям общ делител по-голям или равен на к.

Примерен вход

11 27 8

Примерен изход

11 22

12 24

13 26

16 24

18 27

Решение

За решението на задачата ще използваме алгоритъма на Евклид за намиране на най-голям делител на две числа a и b. Алгоритъмът на Евклид е следния:

1. 
   Докато числата не са равни повтаряме следното:
   

• 
  ако a>b намаляваме b с a;
  
• 
  в противен случай намаляваме a с b;
  

2. 
   Когато двете числа се изравнят, е намерен най-големият им общ делител и той е равен на получената една и съща стойност за двете числа.
   

На базата на така описания алгоритъм можем да съставим функция, която да приема като параметри числата, чийто НОД търсим и връща като резултат намерения НОД. Както параметрите, така и типа на функцията са цели числа. Ето вида на функцията, която пресмята НОД на числата a и b.

int NOD(int a,int b)

{

while(a!=b)

if(a

else a-=b;

return a;

}

За да намерим всички двойки числа в интервала [m, n], които имат най-голям общ делител по-голям или равен на к, е необходимо да разгледаме всички възможни двойки числа в този интервал и за всяка да проверим дали отговаря на условието и ако е така – да я изведем на екрана. Обхождането на всички двойки ще реализираме чрез два вложени цикъла for, в единия от които управляващата променлива i приема последователно като стойности всички числа в интервала, а другия обхожда всички числа от i+1 до края на интервала n. За всяка получена двойка се проверява дали резултатът от функцията NOD е по-голям от к. Ако е така, съответната двойка се извежда на екрана. Функцията main има следния вид:

void main()

{

int m,n,k;

cin>>m>>n>>k;

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

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

if(NOD(i,j)>=k) cout<

}

Задача 3. Сума от цифри

Да се състави програма SUMDIGIT.CPP, която въвежда от клавиатурата две цели числа L и K и извежда всички числа в интервала [L, K], които имат сума от цифрите, кратна на 11 .

Примерен вход

545 597

Примерен изход

551

560

589

Решение

За решението на задачата ще използваме допълнителна функция, която по дадено цяло число пресмята сумата от цифрите му. Вече сме решавали задачата за пресмятане на сумата от цифрите на едно число. Това което трябва да съобразим в момента е как да оформим решението като функция, да опишем нейните параметри и стойността, която връща. Функцията ще има следния вид:

int Suma(int a)

{

int Sum=0;

while(a)

{

Sum+=a%10;

a/=10;

}

return Sum;

}

В главната функция, ще прочитаме двете числа L и K, определящи краищата на интервала, след което ще организираме цикъл for, който обхожда всички цели числа в интервала [L, K] и за всяко от тях проверява дали е кратно на 11. Ако това е така, отпечатва съответното число.

Ето вида на главната функция:

void main()

{

int K,L,n;

cin>>K>>L;

for(n=K;n<=L;n++)

if (!(Suma(n)%11)) cout<}

Задача 4. Дружествени числа

Да се състави програма FRIENDS.CPP, която по зададен интервал [K,L] (K и L цели положителни) извежда на екрана двете най-големи приятелски числа в този интервал. K и L се въвеждат от клавиатурата. Две числа са приятелски ако са прости и разликата им по модул е равна на 2.

Примерен вход

10 50

Примерен изход

43 41

Решение

Тук очевидно ще ни трябва разгледаната вече от нас функция simple, използвана в първата програма на този раздел. Трябва да съобразим, че най-бързия начин да намерим най-голямата двойка приятелски числа в интервала [K,L] е да започнем обхождането на интервала отзад напред, като на всяка стъпка проверяваме дали числото, което е с 2 по-малко от текущото и текущото са прости. Ако това е така, означава, че сме намерили двойка приятелски числа и тя е най-голямата, което означава, че трябва да преустановим търсенето. Това ще се осъществи с оператор break.

Ето текста на цялата програма:

//friends.cpp

#include

#include

int simple(int x)

{

for(int d=2;d<=sqrt(x);d++)

if(x%d==0)return 0;

return 1;

}

void main()

{

int m,n;

cin>>m>>n;

for(int i=n;i>=m;i--)

{

int j=i-2;

if(simple(i)&&simple(j))

{

cout<

break;

}

}

}

3. 
   Задачи за упражнение
   

Зад. 1. Две числа са дружествени, ако сумата от делителите на едното е равна на другото и обратно - сумата от делителите на второто число е равна на първото. Нека да номерираме, двойките дружествени числа в даден интервал с числата 1, 2, 3.., започвайки от първата намерена двойка в интервала. Тогава на всяка двойка ще съответства едно цяло число, което ще наречем пореден номер. Да се състави програма FREND.CPP, която по зададен интервал [K,L] (K и L цели положителни) отпечатва онази двойка дружествени числа, която има пореден номер половината от общият им брой в интервала. K и L се въвеждат от клавиатурата.

Каталог: tadmin -> upload -> storage
storage -> Литература на факта. Аналитизъм. Интерпретативни стратегии. Въпроси и задачи
storage -> Лекция №2 Същност на цифровите изображения Въпрос. Основни положения от теория на сигналите
storage -> Лекция 5 система за вторична радиолокация
storage -> Толерантност и етничност в медийния дискурс
storage -> Ethnicity and tolerance in media discourse revisited Desislava St. Cheshmedzhieva-Stoycheva abstract
storage -> Тест №1 Отбележете невярното твърдение за подчертаните думи
storage -> Лекции по Въведение в статистиката
storage -> Търсене на живот във вселената увод
storage -> Еп. Константинови четения – 2010 г някои аспекти на концептуализация на богатството в руски и турски език

Изтегляне 1.86 Mb.

Сподели с приятели: