Дано число n, подсчитать количество единиц в двоичной записи этого числа

Министерство образования  и науки Республики Казахстан

Международная Бизнес Академия

Бизнес -  колледж

 

 

 

Курсовая работа

По дисциплине: ”Программирование”

На тему: ”Дано число n, подсчитать количество единиц в двоичной записи этого числа”.

 

 

 

 

 

 

 

                                                    Выполнил:     учащийся группы кИС – 10

                                                                           Ситников Сергей Анатольевич

                                                         Проверил:      ст. преп. Кафедры ИТ и ОТД

                                                                                 Краснов А.М.

 

 

 

 

Караганда 2012

Лист индивидуального  задания на курсовую работу по программированию

Учащегося группы кИС-10 Ситникова Сергея Анатольевича

 

Задача: Дано число M в степени n, n - в пределе 1000.

Показать сколько раз  повторяются числа с 0 до 9 включительно.

1. Постановка задачи и пред проектное исследование.
2. Математическая модель поставленной задачи.
3. Алгоритм и блок-схема работы программы
4. Разработка принципов работы программы и проектирование интерфейса.
5. Описание основных процедур и функций программы.
6. Проверка работоспособности и доказательство правильности работы программного обеспечения.
7. Инструкция пользователя.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание принял к исполнению 10.09.12 Ситников Сергей Анатольевич.

 

Дата предоставления оконченного  задания 20.11.12

Содержание:

1. Постановка задачи и пред проектное исследование    4
2. Математическая модель поставленной задачи     8
3. Алгоритм и блок-схема работы программы            12
4. Разработка принципов работы программы и проектирование интерфейса                  16
5. Описание основных процедур и функций программ           21
6. Проверка работоспособности и доказательство правильности работы ПО                   26
7. Инструкция пользователя               28

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Постановка  задачи.

Подсчет количества чисел от 0 до 9 в числе М в степени n.

Цель – изучение методики подсчета количества чисел М в степени n, от 0 до 9.

Исходными условиями (дано) являются:

1. Введение пользователем натурального числа М в степени n;

2. Методические материалы;

3. Язык разработки freepascal.

Критерий эффективности  разработки:

- Корректный подсчет количества чисел из числа M в степени n, ведеными пользователем;

- обработка исключительных ситуаций;

- результаты тестирования;

Требуется:

1. Изучить способы возведения числа в степень.
2. Разработать математическую модель подсчета количества чисел в числе M в степени n, введенные пользователем;
3. Построить различные известные алгоритмы подсчета значащих битов в двоичном представлении числа;
4. Провести анализ эффективности представленных алгоритмов;
5. Разработать на языке free Pascal программный продукт, реализующий алгоритм подсчета чисел в числе M в степени n, которые ввел пользователь;
6. Разработать набор тестов, демонстрирующих корректность работы программного обеспечения.

Введение

 

Начнём с того что язык программирования Pascal отличается от большинства других тем, что в нем отсутствует оператор возведения в степень. Поэтому фрагмент программы для осуществления этого математического действия приходится составлять самостоятельно.

Рассмотрим способы возведения в степень в Pascal.

1- Наиболее простой случай возникает, когда число необходимо возвести в небольшую целую положительную степень. Такое математическое действие можно выполнить буквально за одну строку. Например, если число необходимо всегда возводить в четвертую степень, воспользуйтесь такой строкой:

b:=a*a*a*a;

Сами переменные a и b должны иметь тип, соответствующий диапазону  и виду чисел, подвергающихся возведению в степень.

2- Если число также возводится в целую и положительную степень, но она велика, и, к тому же, может меняться, воспользуйтесь циклом. Для этого поместите в программу такой фрагмент:

c:=a;

 if b=0 then c:=1;

 if b>=2 then for i:=2 to b do c:=a*c;

Здесь a - число, подлежащее возведению в степень, b - показатель степени, c - результат. Переменные i и b - обязательно  типа integer.

 

 

3- Чтобы возвести число в дробную степень, воспользуйтесь свойствами логарифмов. Соответствующий фрагмент программы при этом будет выглядеть так:

c:=exp(b*ln(a));

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

if a=0 then c:=1 else c:=exp(b*ln(a));

Это позволит обойти ограничение  на диапазон значений входного параметра  натурального логарифма, который при  нуле не имеет математического смысла. Второй недостаток, однако, останется  в силе: возводить в степень  отрицательные числа по прежнему не удастся. Все переменные используйте типа real.

4- Чтобы возвести в степень отрицательное число, возьмите его модуль, подставьте в предыдущее выражение, после чего поменяйте знак результата. На языке Паскаль это будет выглядеть следующим образом:

c:=(-1)*exp(b*ln(abs(a)));

Затем, если сама степень  является четной, возьмите модуль от результата:

if round(b/2)=b/2 then c:=abs(c);

 

 

 

 

5- Иногда возникает необходимость в универсальном фрагменте программы, позволяющем осуществлять возведение в степень в отношении любых чисел. Тогда составьте его следующим образом:

c:=0;

 if a if a>0 then c:=exp(b*ln(a));

 if b=0 then c:=1;

 if round(b/2)=b/2 then c:=abs(c);

Здесь все переменные - также  типа real.

Из приведённых выше способов возведения в квадрат нам наиболее подходит 3 способ. Потому-что в условии задачи нас просят возвести некое число M в некую степень n.

То есть для решения  задачи по условию я буду использовать вот эту формулу:

c:=exp(b*ln(a));

Так как она больше всего  для нас подходит для того чтобы возвести число в дробную степень.

 

 

 

 

 

 

2. Математическая  модель.

В блоке описания переменных (var) описываются переменные, которые использует данное приложение.

В данном приложении необходимо использовать 8 переменных:

Основные переменные:

• М, n-числа вводимые пользователем.

Нам так же понадобятся:

• i, b, c-числа подсчета данных.
• S- используется для вычисления чисел M в степени n.
• strl, sr-используются для вывода и получения ответа.

Существует итеративный (циклический) и рекурсивный подходы к решению данной задачи.

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

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

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

Итерация в программировании — организация обработки данных, при которой действия повторяются  многократно, не приводя при этом к вызовам самих себя (не путать с рекурсией)

 

 

Когда какое-то действие необходимо повторить большое количество раз, в программировании используются циклы. Например, нужно вывести 200 раз на экран текст «Hello, World!». Вместо двухсоткратного повторения одной и той же команды вывода текста часто создается цикл, который проходится 200 раз, и 200 раз выполняет то, что написано в теле цикла. Один шаг цикла и называется итерацией.   

Теорема. Произвольный алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационной форме и наоборот.  

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

I) условие продолжения  рекурсии (шаг рекурсии);  

 II) условие окончания рекурсии.

И так как мы знаем какие существуют функции для целых переменных. Это нахождение модуля числа (Функция Abc), а также возведение числа в квадрат (Функция Sqr). В этом уроке мы рассмотрим функции, применяемые к дробным числам. Это функции:

 Sqr - квадрат числа,

 Abs - модуль числа,

 Sqrt - корень числа,

а также известные всем математические функции:

 Sin, Cos, Arctan, Ln, Exp, Pi.

 

 

Но нам нужны будут  только : Exp, Ln.

Функция Exp возводит число «e» (экспонента - 2.72...) в степень, значение которой указывается в скобках после слова Exp. Т.е. в нашем случае число «e» будет возведено в степень «2».

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

И как говорилось выше, мы будем использовать формулу:

c:=exp(b*ln(a));

Для поиска схожих чисел  от 0 до 9. Нам понадобиться открывать  цикл.

Существует 3 вида цикла:

1. For
2. While
3. Repeat
1. Часто цикл for называют циклом со счетчиком. Этот цикл используется, когда число повторений не связано с тем, что происходит в теле цикла. Т.е. количество повторений может быть вычислено заранее
2. Цикл while является циклом с предусловием. В заголовке цикла находится логическое выражение. Если оно возвращает true, то тело цикла выполняется, если false – то нет.

То есть while может не выполниться ни разу, если логическое выражение в заголовке сразу вернуло false.

3. В цикле repeat логическое выражение стоит после тела цикла. Причем, в отличие от цикла while, здесь всё наоборот: в случае true происходит выход из цикла, в случае false – его повторение.

Сделаем выводы, нам наиболее лучше подходит цикл while. Так как у нас имеется пред условие, его удобно использовать для поиска схожих цифр от 0 до 9. Мы сделаем так:

while c<=9 do begin

      ***- некое условие или действие, переменная

Далее воспользуемся циклом for для подсчёта схожих чисел:

      for i:=1 to length(***) do

         begin

          if *** then ***;end;

      И сделаем вывод:

form1.Memo1.Lines.Add (***)

Length - эта функция возвращает динамическую длину строки. То есть:

Функция возвращает в качестве результата значение текущей длины  строки-параметра 

Пример:

n := length('Pascal'); {n будет равно 6}

Concat(s1,[s2,...,sn]:string):string

 

 

 

 

3. Алгоритм  и блок схема работа программы.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Построим блок-схему while (Рис. 1.1)

Линейный алгоритм или  следование – это тип алгоритма, в котором последовательность действий не меняется в его процессе выполнения.

На практике линейные алгоритмы  в чистом виде встречаются редко: при расчете арифметических и  алгебраических выражений, при расчете  по формулам, при решении ряда бытовых  задач.

Рекурсивный- алгоритм эквивалентен по сложности исходя из теоремы об эквивалентности циклических и рекурсивных алгоритмов.