Задача на одномерные массивы

ФЕДЕРАЛЬНОЕ АГЕНТСТВО  ПО ОБРАЗОВАНИЮ

 

 

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

 

Московский  государственный университет

приборостроения и информатики

 

 

 

 

 

 

 

 

ПОСОБИЕ ПО ИНФОРМАТИКЕ

 

для слушателей

 

подготовительных  курсов

 

Учебное пособие

 

 

 

 

 

 

 

Москва

2007

 

 

 

 

 

 

 

 

 

 

 

 

УДК 004517

ББК32.81

 

 

Пособие по информатике  для слушателей подготовительных курсов МГУПИ. Учебное пособие/ Журавлев В.А., Карулина В.А., Письменная Е.В.: Москва, МГУПИ, 2007.

 

 

Предлагаемое пособие  предназначено для слушателей подготовительных курсов Московского Государственного Университета Приборостроения и  Информатики и содержит разбор задач различных разделов информатики, а так же варианты тестов для самостоятельного решения.

Пособие обобщает опыт проведения вступительных экзаменов по информатике в форме тестирования в МГУПИ.  Оно будет  полезным также преподавателям, ведущим занятия на подготовительных курсах и других подразделениях, осуществляющих подготовку к вступительным экзаменам по информатике в МГУПИ.

 

 

 

Печатается по решению  Редакционно-издательского совета Московского 

Государственного Университета Приборостроения и Информатики.

 

 

 

Рецензент: Филатов

 

 

 

© Московский Государственный Университет

Приборостроения и Информатки.

© Журавлев В.А., Карулина В.А., Письменная Е.В.

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

 

Пособие предназначено  старшеклассникам и абитуриентам для  подготовки к вступительным экзаменам в МГУПИ. Пособие составлено в соответствии со школьной программой курса «Информатика» и в соответствии с примерной программой вступительного экзамена по основам информатики и вычислительной техники в вузы России [http://www.edu-it.ru/docs/sch_inform]. В пособии рассмотрены арифметические и логические основы ЭВМ, особое внимание уделено основам алгоритмизации и программирования. Проанализированы типовые алгоритмы и задачи на знание основ программирования. В качестве языка программирования выбран школьный алгоритмический язык.

Пособие знакомит будущих абитуриентов с образцами зданий, демонстрирует методы решения задач различной сложности.

Вступительные экзамены по информатике в МГУПИ проводятся в форме тестирования. Задания теста содержат 10 заданий. Первые восемь заданий с выбором ответа. Последние два задания без ответов. На выполнение экзаменационной работы по информатике отводится 3 часа (180 минут).

В 2007 году задачи представлены из следующих разделов:

1. Системы счисления;

2. Арифметические операции в системе чисел;

3. Хранение данных в ЭВМ;

4. Элементы математической логики;

5. Основные логические и запоминающие элементы компьютера;

6. Алгоритмизация и программирование;

7. Решение типовых  задач.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Системы счисления

 

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

Системы счисления делятся  на непозиционные и позиционные. В непозиционных системах количественное значение символа определяется только его изображением и не зависит от его места (позиции) в числе. Например, римские цифры. Числа обозначались: 1 – I, 2 – II, 3 – III, 4 – IIII, 5 – V, 10 – X. Для более крупных чисел применялись обозначения L – 50;  C – 100; D – 500;  M – 1000. Позже стали применять обозначения 4 – IV;  9 – IX; 40 – XL;  90 – XC, и т.д. Числа обозначались посредством суммирования знаков в записи числа. Например, число 37 обозначалось в виде ХХХVII = 10+10+10+5+2. Этим способом можно записать любое число. Например, число 99 изображается XCIX.  Римская система являлась непозиционной системой счисления, где не представляются дробные и отрицательные числа, действия над числами связаны с большими трудностями и не имеют жестких правил. Поэтому для быстрого выполнения расчетов с большими числами римская система не давала удовлетворительных результатов.

Наряду с римской  системой счисления развивалась  арабская позиционная система счисления, которая оказалась  весьма удобной для реализации данных целей. Это была  позиционная десятичная система чисел, в которой  числа представлялись просто, а операции выполнялись быстро.

Основанием десятичной системы является число 10. Алфавитом  позиционной десятичной системы  являются десять цифр (символов), значения которых зависят от их местоположения в записи числа. В десятичной системе чисел на последнем месте записываются единицы, на предпоследнем – десятки, а перед этим – сотни и т.д.

 

Пример:

552 = 5´100 + 3´10 + 2´1 или 532 = 5´10² +3´10¹ + 2´10⁰

Тем же способом, используя  отрицательные степени 10^-1 = 0,1; 10^-2 = 0,01 и т.д., легко записать и десятичные дроби.

Пример:

0,839 = 8´10^-1 + 3´10^-2 + 9´10^-3

Смешанное число представляется тоже степенным рядом по убыванию степеней основания системы.

Пример:

A₍₁₀₎=552,25=5´10² +5´10¹+ 2´10⁰ + 2´10^-1 +5´10^-2

В десятичном числе A₍₁₀₎  цифры 5 и 2, находящиеся на разных позициях, имеют различные количественные значения, при перемещении цифры на следующую позицию ее величина изменяется в 10 раз.

A₍₁₀₎ = 102,839 = 1´10² + 0´10¹ +2´10⁰ +8´10^-1 +3´10^-2 +9´10^-3

Если вместо 10 взять  любое другое  натуральное число  p > 1, легко построить число в системе счисления с основанием  p.

Пусть, например, p = 2. В этой двоичной системе счисления употребляются  только две цифры:  0 и  1.

11011,011₍₂₎ = 1´2⁴ + 1´2³ + 0´2² +1´2¹ +1´2⁰ + 0´2^-1 + 1´2^-2 = 27,375₍₁₀₎

Каждое целое число  может быть записано в системе  десятичных цифр, т.е. в виде

A₍₁₀₎= a_n´10ⁿ + a_n-1´10^n-1 + …+a₂´10² + a₁´10¹ +a₀ ´10⁰,

где  n – некоторое соответствующее неотрицательное число;  числа a_n, a_n-1, …, a₂, a₁, a₀ — знаки цифр из алфавита  а_i Î {0…9}.

 

Запись  некоторого числа в произвольной системе счисления. Любое число в позиционной системе счисления при любом основании q > 1 может быть записано в естественной форме

может быть представлено степенным рядом

,

где а_k — любая цифра из алфавита системы основания p, m, 1 — число позиций (разрядов) соответственно для целой и дробной частей числа. Для удобства преобразования чисел из одной системы счисления в другую степенной ряд для целой и дробной частей числа представляется эквивалентными выражениями по схеме Горнера:

 

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

Прибавление единицы  к более старшему (k+1)–му разряду происходит, когда число, составленное из оставшихся более младших k разрядов составляет p^k - 1.

Пример:  p = 2, число 0111₍₂₎+1 дает переход единицы из нулевого разряда в первый (в нулевом разряде остался 0),  далее из первого во второй (в первом разряде остался 0),  и  далее  в третий,  в  результате чего получится  число  0111₍₂₎ + 1 = 7₍₁₀₎ +1 = 8₍₁₀₎ = 2³  =  1000₍₂₎, k  = 3.

 

 

p=10	p=2	p=3	p=4	p=5	p=6	p=7	p=8	p=9	p=16	p=27
0	0000	0000	0000	0000		000	00	000	0	0
1	0001	0001	0001	0001			01		1	1
2	0010	0002	0002	0002			02		2	2
3	0011	0010	0003				03		3	3
4	0100	0011	0010	0004			04		4	4
5	0101	0012	0011			005	05		5	5
6	0110	0020	0012	0011			06		6	6
7	0111	0021	0013			010	07		7	7
8	1000	0022	0020				010	008	8	8
9		0100						010	9	9
10		0101		0020		013			A	A
11		0102							B	B
12		0110							C	C
13		0111				016			D	D
14		0112							E	E
15	01111	0120	0033	0030			017		F	F
16								017	10	G
17						023			12	H
18									13	I
19				0034					14	J
20									15	K
21	10101							024	16	L
22									17	M
23									18	N
24				0044					19	J
25									1A	P
26										Q
27	11011									10

 

Для проверки правильности заполнения пустых клеток необходимо выполнить обратный перевод записанных чисел. Для этого нужно использовать формулу для перевода  числа из  системы счисления с основанием  p  в систему счисления с основанием 10 следующим образом. Например, вписанное число 221₍₃₎ = A₍₁₀₎ = 2´3²+2´3¹+1´3⁰ = 25, что соответствует числу, расположенному в соответствующей ячейке десятичной системы счисления.

Перевод числа с основанием, являющимся степенью другой системы. Если между основаниями p и q соблюдается связь р¹ = q^k , где k – целое, то каждая цифра числа с основанием p представляется k цифрами алфавита основания q. Так, если   p¹ = 8¹ = q^k = 2³ или  p¹ = 27¹ = q^k = 3³ то каждая цифра p–го числа (восьмеричного  или   двадцатиcемиричного)   представляется   k   (тремя)   цифрами q–ричного (двоичного или троичного) числа и наоборот — каждая группа из k цифр (от запятой влево и вправо) q–ричного числа заменяется одной   p–ричной цифрой  (см. в таблице столбцы, выделенные жирным шрифтом и выделенные другим шрифтом).

 

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

1. А₍₈₎ = 407,15 = A₍₂₎= 100 000 111,001 101    и обратно    А₍₂₎= 10 011 011,010 11 = =A₍₈₎= 233,26.
2. B₍₂₇₎ = 23D,23 = B₍₃₎=2 010 111,002 01 и обратно B₍₃₎ = 210110,22102 = B₍₉₎ = =713,836.
3. B₍₉₎  = 78.457 = B₍₃₎ = 2122.111221    и обратно B₍₃₎ = 221221001.12021 = B₍₂₇₎ = =PP1.FK
4. C₍₁₆₎ = 4F0E,1C = С₍₂₎ = 0100111100001110,00011100;

     C₍₂₎= 11001101011,111101 = C₍₁₆₎ =  =66B,F4

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

Такие преобразования используются для сокращения записи двоичных чисел, при переводе чисел из десятичной системы счисления в двоичную, а также при выполнении некоторых  операций в ЭВМ.

 

Перевод целых чисел из одной системы  счисления p в другую систему с основанием q. Целое число в системе счисления p может быть представлено эквивалентным числом в системе счисления q:

A_p = A_q = (…((b_n-1q + b _n-2)q + b_n-3)q +… +b₁)q + b₀     

Задача перевода числа  из одной системы счисления (p) в другую (q)  заключается в отыскании значений цифр b_k числа в новой системе счисления. 

Заметим, или А_p = А_q = (А_q)₁×q + b₀, где (А_q)₁ — целое частное, полученное при делении А_p  на основание q, b₀ – остаток, являющийся первой младшей цифрой числа в новой системе  счисления, выражен цифрами исходной системы счисления.