lektsii_po_infe
.pdf
71
#include <stdlib.h> //файл с описанием функции rand() void main()
{
int a[100]; int n;
cout<<”\nEnter the size of array:”;cin>>n; for(int I=0;I<n;I++)
{
a[I]=rand()%100;// числа из диапазона 0..100 cout<<a[I]<<” ”; //выводэлементамассива
}
}
Задача3 |
. Найти максимальный элементмассива. |
||
Длярешеэтойзадачинияужно |
|
сформиромасс,прначальноеввзначениеатьоитьв |
|
переменную max,вкачественачальногозначениявыступаетпервыйэлементмассива, |
|||
затемсравнитькаждыйэлементмассивапеременной |
max.Еслизначэлебудниеменета |
||
больше max,тоегозначениезаписывается |
max ипоследующэлементысравниваютсяе |
||
ужесэтимзначение |
м. |
|
|
#include <iostream.h> #include <stdlib.h> void main()
{
int a[100]; int n;
cout<<”\nEnter the size of array:”; cin>>n;
for(int I=0;I<n;I++) //заполнение массива
{
a[I]=rand()%100-50; cout<<a[I]<<” ”;
} |
|
|
|
int max=a[0]; |
//задначальноеемзначение |
max |
|
for(I=1;I<n;I++) |
|
||
//сравниваемэлементыма сива |
max |
|
|
|
if(a[I]>max)max=a[I]; |
|
|
cout<<”\nMax=”<<max; |
|
||
} |
|
|
|
Задача3 |
. Найтисумму |
элеменмассчетиновваымидексами. |
|
Длярешенияэтойзадачиможнопредложитьнеспособовколько. |
|
|
|
1. Массивперебшагоми2рается |
всеэлементысуммируются. |
|
|
2.Массивперебшагоми1сураетсятолькомируютсяэлеменчетны,имеющие индексы.Дляпроверкиначетностьисп перацияльзуетсяполученияостаткаот деленияна2.
//Первый способ
#include <iostream.h>
72
#include <stdlib.h> |
|
void main() |
|
{ |
|
int a[100]; |
|
int n; |
|
cout<<”\nEnter the size of array:”; |
|
cin>>n; |
|
for(int I=0;I<n;I++) |
|
{ |
|
//заполненмаслучсиваесламийными |
|
a[I]=rand()%100-50; |
|
cout<<a[I]<<” ”; |
|
} |
|
int Sum=0; |
|
for(I=0; I<n; I+=2) |
д. |
//суммируютсяэлементыиндексами0,т.2, 4, |
|
Sum+=a[I]; |
|
cout<<”\nSum=”<<Sum”; |
|
} |
|
|
|
//Второй способ |
|
#include <iostream.h> |
|
#include <stdlib.h> |
|
void main() |
|
{ |
|
int a[100]; |
|
int n; |
|
cout<<”\nEnter the size of array:”; |
|
cin>>n; |
|
for(int I=0;I<n;I++) |
|
{ |
|
//заполненмаслучсиваесламийными |
|
a[I]=rand()%100-50; |
|
cout<<a[I]<<” ”; |
|
} |
|
int Sum=0; |
|
for(I=0; I<n; I++) |
|
if(I%2==0) |
|
//суммируютсяэлементыиндексами0,т..2, 4, |
|
Sum+=a[I]; |
|
cout<<”\nSum=”<<Sum”; |
|
} |
|
19.3.Переборэлементовмассива
1) |
Элементымассиваожнобрабатыпоодноэле,двигаясьментуать |
отначала |
|
массикегок или(нцувобранатномправлении): |
a[i]> |
|
for(int i=0;i<n;i++)обработка< |
|
2) |
Элементымассиваожнобрабатыватьподваэлемента,двигаясьобеихсторон |
|
|
маскегосерединеива: |
|
|
int i=0,j=n-1; |
|
|
|
73 |
while (j<j){ |
a[j]>; |
|
<обработка |
a[I]и |
|
i++;j++;} |
|
|
3) Элементымассиваожнобрабатыватьподваэлеме,двигаясьотначалатак |
|
|
концусшагом1(т.е.обрабатпарэлементовываются |
a[0]и a[1], a[1]и a[2]ит.д.) |
|
for(i=0;i<n-1;i++) |
|
|
<обработкаa[i]и a[i+1]> |
|
|
4) Элементымассиваожнобрабатыватьподваэ |
леме,двигаясьотначалатак |
|
концусшагом2(т.е.обрабатпарэлементовываются |
a[0]и a[1], a[2]и a[3]ит.д.) |
|
i=1; |
|
|
while(i<n){ |
a[i]и |
a[i+1]> |
<обработка |
||
i:=i+2;} |
|
|
19.4.Классызадачпообработкемассивов
1) |
Кзадачамкласса1 относятсязадачи,вкоторых |
выполняетсяоднотипнаяобработка |
|
всехилиуказанныхэлеменмассива.Решениетовакихз сводитсядачк |
|
|
устантого,какобрабатываевлениюкаждыйэлементмассилуказанныеисява |
|
|
элементы,затемподбираподходящаясхпереборатсяма,вкоторуювставляются |
|
|
операторыобработкиэлементовмассива.Примеромтакойзадачиявляется |
|
|
нахожсреарифмдениенегоэлемассиватическогоментов. |
|
2) |
Кзадачамкласса2 относятсязадачи,вкоторыхизменяпорядокслетсядования |
|
|
элементовмассива.Обменэлементоввнмассиваутривыполн |
яется |
использованиемвспомогатперем: льнойнной
R=a[I];a[I]=a[J]; a[J]=R;//обмен a[I]и a[J]элементов массива.
3) |
Кзадачамкласса3 относятсязадачи,вкоторыхвыполняетсяобработканескольких |
|
|
|
массподмассивовмассиваили одного.Массивыгутбрабат |
ыватьсяпо |
|
|
однойсхеме |
– синхроннаяобработкаилипоразнымсхемам |
– асинхронная |
|
обработкамассивов. |
|
|
4) |
Кзадачамкласса4 относязадачи,вкотребуетсяорыхотыскатьпервый |
|
|
|
элементма,совпсивазадазначениемющийнным |
– поисковыезадачи |
|
|
массиве. |
|
|
19.5.Сортировкамассивов
Сортировка – этопроцессперегруппировкизадамнногобъектовжества некоустанорпорядке.вленном
19.5.1Сортир. спомощьювключениявка
|
Элемемассиваделятсянаужетыготповуюследовательностьиисходную.При |
|
|||||||
каждомшаге,начинаяс |
|
|
|
I=2,изисхподнойследовательностиизвлекается |
i-ыйэлементи |
||||
вставляетсянанужноемесгоптовойследовательности,затем |
i увелнаи1т.чивается |
||||||||
д. |
|
|
|
|
|
|
|
|
|
4 |
4 |
5 |
2 |
2 |
4 |
|
8 |
|
|
|
|
|
|
||||||
отовая |
г |
|
|
исходная |
|
||||
Впроцепоинужногосмсекастаущпествляютсяресылкиэлементовбольше |
|
||||||||
|
|
||||||||
выбранаодпозициюнвправоуного,т.е.выбранныйэлементсравниваюточередным |
|
||||||||
элементомотсортированнойчасти,начиная |
|
|
|
j:=i-1Есливыбранный. элементбольше |
a[i], |
||||
тоеговключаютотсортичасть,прослучаетивванномую |
|
|
a[j]сдвигаютнаодну |
||||||
позицию,авыбранныйэлементсравнивасоследуэлементомющимсортированной
74
последовательности.Процесспоискаподходящегоместаза |
канчиваетсяпридвух |
|
различныхусловиях: |
|
|
- |
еслинайденэлемент |
a[j]>a[i]; |
- |
достилевыйкогнотецпутовойследовательности. |
|
int i,j,x; for(i=1;i<n;i++)
{
x=a[i];//запомнилиэлемент,которыйбудемвставлять j=i-1;
while(x<a[j]&&j>=0)//поискподходящего места
{
a[j+1]=a[j];//сдвигвправо j--;
}
a[j+1]=x;//вставкаэлемента
}
19.5.2Сорти. методомпростоговыборавка
|
|
Выбмираетсяниэлементассивальныйменяемеспервымтамися |
|
||||
элеменмассива.Запроцесстомповторяетсятавшимисяэлементами |
ит.д. |
||||||
4 |
5 |
2 |
2 |
4 |
8 |
|
|
|
|
ин |
|
|
|
|
|
int i,min,n_min,j; for(i=0;i<n-1;i++)
{
min=a[i];n_min=i;//поиск минимального for(j=i+1;j<n;j++)
if(a[j]<min)
{
min=a[j]; n_min=j;
}
a[n_обменmin]=a[i];// a[i]=min;
}
19.5.3Сорти. методомпростогобвкаена
Сравниваютсяменяютсяместамипарыэлементов,начинаяспоследнего.В результатесамаленькийыйэлементмассиваоказываетсясамымлевымэле ентом массива.Процессповторяетсяоставшимисяэле ассиваентами.
4 |
5 |
2 |
2 |
4 |
|
for(int i=1;i<n;i++) for(int j=n-1;j>=i;j--)
if(a[j]<a[j-1])
75
{
int r=a[j]; a[j]=a[j-1]; a[j-1]=r;}
}
19.6.Пвотсортирои кмассивеанном
|
|
|
Вотсортмасисропользуетсяидихотомическийванномбинарный( )поиск.При |
|
|
|
|||||||
последоватпоискетребуетсяср льномднем |
|
|
|
|
|
n/2срав нений,где |
n – количество |
||||||
элевмассентов.Прид хотвепоискетремическомнеболееуется |
|
|
|
n<k=2m. |
m сравнений,если |
||||||||
n- m-аястепень2,если |
|
n неявлясте2,топеньюся |
|
||||||||||
|
|
|
|
|
Массделпополамивтся |
|
|
|
S:=(L+R)/ 2+1 иопределяетсявкакойчасти |
||||
массиванаходитсянужныйэлементХ.Таккакмассивупорядочен,то,если |
|
|
|
|
a[S]<X – |
||||||||
искомыйэлементнаходитсявправойчастимассива,иначе |
|
|
|
|
|
– находитсявлевойчасти. |
|||||||
Выбранчастьмассинадоовауюразделитьпополам.., |
|
|
|
|
|
|
дотехпор,покагр ницы |
||||||
отрезка L и R нестанутравны. |
|
|
|
|
|
||||||||
1 |
3 |
8 |
|
10 |
11 |
15 |
19 |
|
21 |
23 |
37 |
|
|
0 |
1 |
2 |
|
3 |
4 |
5 |
6 |
|
7 |
8 |
9 |
R |
|
|
|
|
L |
|
|
S |
|
|
|
|
|||
int b; cout<<"\nB=?";cin>>b; int l=0,r=n-1,s;
do
{
s=(l+r)/2;//среднийэлемент if(a[s]<b)l=s+1;//перенестилеуюграницу else r=s;//перенестиправуюгран цу
}while(l!=r); if(a[l]==b)return l; else return -1;
…
20Примеры. задачдляподготовкиэкзамену
Примерызадач |
|
|
|
|
|
|
|
|
2. |
S=1!+2!+3!+. . . N! |
|
|
|||||
3. |
S=1+x1+ x2+ x3+. . .+ xn |
|||||||
|
|
x2 |
|
x3 |
|
xn |
||
4. |
S = x − |
|
+ |
|
|
−... |
|
(−1)n+1 |
2! |
3! |
|
|
|||||
|
|
|
|
|
n! |
|||
5. |
S=15+17-19+21+23-25+…, всего n слагаемых; |
|||||||
6. |
S = sin X + sin 2 |
X + sin 3 X + sin 4 X + ... + sin n X |
||||||
7.S = 
3 + 
6 + 
9 + ....
99
8.S = sin( x + cos(2x − sin(3x + cos(4x + sin(5x − cos(6x + ...)...)
76
9. |
Найтипервоеотрицатечислопоследовательностиьное |
u=cos(ctg(n)),где |
|
|
n=1,2,3…. |
|
|
10. |
Определитьяв числояется |
|
k степенью3. |
11. |
Определитьяв числояется |
|
k простым. |
12. |
Данапоследовательностьиз100 |
|
чисел.Найтиномерпервогоотрицательного |
|
числа. |
|
|
13. |
Найтиколцифрвдчесчислеятичномтво |
|
k. |
14. |
Найтисуммуцифрвдесятичномчисле |
|
k. |
15. |
Сформировать n чиселФибоначчи. |
|
|
16. |
Найтимаксимальныйр |
едичетныхэлементовпоследовательности. |
|
17.НайтиминимальныйсредиэлементовпоследовательностикратныхК.
18.Данмассцелыхчи.Пвс ревернутьлмассив.
19.Данмассцелыхчи.Повселместаенятьэлемассиваенты(01,3,и2и54
|
т.д.). |
|
20. |
Данмассцелыхчи.Сдвселциклическинутьмассивна |
k элемвлентовво |
|
(вправо). |
|
21. |
Данмассцелыхчи.Сдвселциклическинутьмассивна |
k элементвправ. ов |
22. |
Данымасостоящиева2 , целыхзчисел.ПомассивучитьС,гдеС |
i=А i+В i. |
23. |
Удалитьвсеч элементные |
тыизмассцелыхчи. васел |
24.Добавиотрицательногопослекаждого0 элемента.
25.Переставиэлемассивеентытакимобразомь,чтобысначалашливсе
|
отрицательныеэлементы,затемположительные,затемнули. |
|
26. |
Найтипервыйотрицательныйэлементводномерноммасс |
иве. |
27. |
Найтиудалитьпервыйчетныйэлементмассиве. |
|
28. |
Найтимаксимальныйизчетныхэлементовмассива. |
|
Длякажзадоачибытьлжнайсоставленаспецификацтребований,алгор, ятм программаинабортестов.
Оглавление)
1Инфо. ,ееприедметзадачиматика.Оснпоинформатикинятиявые.Информация |
|
|||
формыеепредставления. |
|
......................................................................................................... 2! |
||
2. Инфопр.Фазыминформационногонныйоцесспроцесса |
|
....................................... 4! |
||
3Количество. информации |
|
...................................................................................................... |
5! |
|
3Энтропийный.1. способ |
|
..................................................................................................... |
5! |
|
3Объемныйспособ.2. изм |
|
|
ереинформацииия ................................................................. |
6! |
4Качество. информации |
|
|
.......................................................................................................... |
7! |
5Системы. счисления |
|
............................................................................................................... |
|
8! |
5Позиционные.1. сисчислениятемы |
|
................................................................................ |
8! |
|
5Перевод.2.чизоднойселССругую |
|
.......................................................................... |
9! |
|
5Смешанные.3. СС |
|
............................................................................................................. |
|
10! |
6Кодирование. информации |
|
................................................................................................. |
12! |
|
6Цели.1кодирования. |
|
........................................................................................................ 12! |
||
6Понятие.2.специальномкодировании |
........................................................................ |
12! |
||
7Внутрен. представлениеанныхпамятиееЭВМ |
|
......................................................... |
15! |
|
7Числа.1.фиксированнойточкой. |
................................................................................. 15! |
|||
7Числа.2.плавающейточкой |
|
......................................................................................... |
15! |
|
7Символы.3. |
........................................................................................................................ 16! |
|||
7Кодирование.4. |
графическойинформации .................................................................... |
17! |
||
7Кодирование.5. звуковинф рмациий |
.......................................................................... |
18! |
||
8Понятие. арх принципытектурыустройвычислительныхтваистем ..................... |
19! |
|||
|
|
|
|
|
77 |
8Принципыустройства.1. |
|
................................................................................................. 20! |
|||
8Особенности.2. выпк лнениясокращенныммандколичествомадресныхполей |
|
23! |
|||
8Понятие.3.способаадр сации |
|
........................................................................................ |
24! |
||
8Система.4.команд |
|
............................................................................................................ |
|
26! |
|
8Сис.5. |
темапрерываний ................................................................................................... |
|
31! |
||
9Жизненный. циклпрограммы |
|
............................................................................................. |
34! |
||
9Понятие.1.парадигмыпрограммирования |
.................................................................... |
34! |
|||
9Жизненный.2. циклпрограммного |
обеспечения .......................................................... |
36! |
|||
10. Сиисртпрограммированияедама |
............................................................................... |
41! |
|||
10Поня.1си. исредтемыиепрограммирования ........................................................ |
41! |
||||
10Общая.2характеристика. п |
латформыMSDN ............................................................. |
43! |
|||
10Версии.3. |
......................................................................................................................... 46! |
||||
11Структура. программынаязыкеC/C++ |
|
............................................................................ |
47! |
||
12Элементы. языкаC/C++ |
|
.................................................................................................... |
|
50! |
|
13Типы.данныхвC/C++ |
|
...................................................................................................... |
|
51! |
|
13Тип.int1. |
.......................................................................................................................... 52! |
||||
13Тип.char2. |
|
....................................................................................................................... 52! |
|||
13Тип.wchar3._t |
|
................................................................................................................. |
|
53! |
|
13Тип.bool4. |
|
....................................................................................................................... 53! |
|||
13Типы.с5. |
|
плавающейточкой |
........................................................................................ |
53! |
|
13Тип.void6. |
|
....................................................................................................................... 53! |
|||
14Переменные. |
................................................................................................................... 53! |
||||
15Выражения. |
......................................................................................................................... 54! |
||||
16Ви.выводданных |
|
........................................................................................................ |
|
55! |
|
17. ОператорыC/C++ |
|
.............................................................................................................. |
|
56! |
|
17Баз.1к.онвыеструктупрогциирногоаммирования ....................................... |
56! |
||||
17Оператор.2выражение.« » |
|
............................................................................................. |
57! |
||
17Составные.3. |
|
операторы ................................................................................................ |
57! |
||
17Операторы.4выбора. |
|
..................................................................................................... 58! |
|||
17.5. Операторы циклов ..................................................................................................... |
|
59! |
|||
17Операторы.6перехода. |
|
.................................................................................................. 61! |
|||
18Примерырешения. задачсиспользосновныхоператоровваниемС++ |
..................... |
62! |
|||
18Программирование.1. ветвлений |
.................................................................................. |
62! |
|||
18Программ.2. арифметическихц рованиеклов |
.......................................................... |
63! |
|||
18Программир.3. итерацицикловваниенных |
.............................................................. |
64! |
|||
18Программир.4. вложенныхциклование |
................................................................... |
68! |
|||
19Массивы. |
............................................................................................................................. 69! |
||||
19Определение.1.массиваC/C++ |
|
.................................................................................. |
69! |
||
19Примеры.2решения. задачиспользованиеммассивов |
........................................... |
70! |
|||
19Перебор.3элементов. массива |
|
...................................................................................... |
72! |
||
19Кл.4за.поссыдачобработкемассивов |
...................................................................... |
73! |
|||
19Сортиро.5.массивовка |
|
................................................................................................. |
73! |
||
20Примерызадач. дляподготовкиэкзамену |
|
.................................................................... |
75! |
||