Дано число 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)

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

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

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

Под алгоритмом обычно понимают четко определенную последовательность действий, приводящую через конечное число шагов к результату —  решению задачи,  для которой разработан алгоритм.

Основные свойства, присущие любому алгоритму:

1. массовость —  алгоритм предназначен для решения задачи с

некоторым множеством допустимых входных данных;

2. конечность —  алгоритм должен завершаться за конечное число

шагов (но это количество шагов, может быть разным для разных

входных данных).

В информатике и теории алгоритмов вычислительная сложность  алгоритма — это функция, определяющая зависимость объёма работы, выполняемой  некоторым алгоритмом, от размера  входных данных. Раздел, изучающий  вычислительную сложность, называется теорией сложности вычислений. Объём  работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством  элементарных шагов, необходимых для  решения проблемы, тогда как пространство определяется объёмом памяти или  места на носителе данных. Таким  образом, в этой области предпринимается  попытка ответить на центральный  вопрос разработки алгоритмов: «как изменится  время исполнения и объём занятой  памяти в зависимости от размера  входа и выхода?». Здесь под  размером входа понимается длина  описания данных задачи в битах (например, в задаче коммивояжера длина входа пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (оптимального маршрута в задаче коммивояжера).

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Разработка принципов работы программы и проектирование интерфейса.

     1

    2

   

      3

    4

    5

    6

 

                                            

 

                             7               

                                                                     8

1. Label1- Условие задачи.
2. Label2- Описание SpinEdit1, в нашем случае : Введите число М.
3. SpinEdit1- Число М.
4. Label3- Описание SpinEdit2.
5. SpinEdit2- Степень N.
6. Button1- Кнопка подсчёта и вывода ответа в Memo1.
7. Label4- посменное направление.
8. Memo1- В этом окне высвечивается ответ при нажатие кнопки Button1.

 

 

 

 

 

 

 

 

 

 

 

 

В среде разработки Lazarus спроектируем интерфейс, разместив на форме управляющие элементы

 

 

Для нашей работы нам потребуется  4 основных компонента:

• Label
• SpinEdit
• Button
• Memo

Разместим их путем перетаскивания на форму.

• Label – В интерфейсе у нас указан в виде текса, к примеру:

Так же

И являются одним из компонентов: Label.

• Число М вводиться в SpinEdit1

Так же как:

• Степень N вводиться в SpinEdit2

Затем для запуска вычисления нажимается кнопка «Ответ» (Button1)

Результат вычислений выводится в компоненте Memo.

 

 

Разработка принципов работы программы

 При запуске приложения  с помощью команды (caption) высвечивается окно:

В котором пользователь может  выбрать Число М в степени  n, и получить ответ нажав на кнопку «Ответ».

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

После чего выполняется возведение числа M в степень n, которые ранее выбрал пользователь.

Далее реализуется цикл, в теле которого производиться подсчёт количества цифр от 0 до 9 из подсчитанной суммы M в степени n.

После того, как подсчет от 0 до 9 закончиться происходит вывод полученного результата в компонент Memo1.

 

То есть в компонент  Memo1 выводиться переменные:

(c)- Числа, которые мы ищем (от 0 до 9)

(strl)- Число полученное в результате возведения числа M в степень n, и в котором мы ищем количество повторений.

(b)- Количество повторяющихся чисел от 0 до 9.

После чего происходит выход из цикла.

Ниже представлен листинг программы с комментариями, алгоритмов возведения числа М в степени n, и подсчёта чисел от 0 до 9.

 

 

 

 

 

 

 

 

 

 

 

 

 

5. Описание основных процедур и функций программ.

Изначально при загрузке приложения выводится команда вывода на экран приглашения ввести число, в котором мы будем подсчитывать число 1 в двоичном представлении:

Label1(Введите число, что бы подсчитать количество 1 в его двоичном представлении).

Листинг программы с постусловием:

(* Начало блока тела программы *)

unit Unit1;

{$mode objfpc}{$H+}

interface

uses

(*Описание используемых модулей*)

  Classes, SysUtils, FileUtil, LResources, Forms, Controls, Graphics, Dialogs,

  Buttons, ComCtrls, Spin, ButtonPanel, StdCtrls, Arrow;

 

 

 

 

 

 

 

 

Type

(*Описание компонентов на форме*)

{ TForm1 }

  TForm1 = class(TForm)

    BitBtn1: TBitBtn;

    Label1: TLabel;

    Label2: TLabel;

    Label3: TLabel;

    Label4: TLabel;

    Memo1: TMemo;

    SpinEdit1: TSpinEdit;

    SpinEdit2: TSpinEdit;

        procedure BitBtn1Click(Sender: TObject);  private

    { private declarations }

  public

    { public declarations }

  end;

 

 

 

 

 

var

(*Главная форма*)

  Form1: TForm1;

implementation

{ TForm1 }

procedure TForm1.Button1Click(Sender: TObject); (*Блок определения переменных, где М и n – вводимые пользователем числа, (b)- Количество повторяющихся чисел от 0 до 9. (c)- Числа, которые мы ищем (от 0 до 9)

(strl)- Число полученное в результате возведения числа M в степень n. Тип переменных- целочисленный.*)

var

n,m,i,b,c:integer;

s:extended;

strl,sr:string;

(* Начало блока тела  программы *)

 

Begin

(* считывание введённого числа *)

m:=strtoint(form1.spinedit1.Text);

n:=strtoint(form1.spinedit3.Text);

 (* Возведение числа М в степень n *)

s:=exp(ln(m)*n);

(*Вывод полученного результата  возведения в степень *)

form1.Memo1.Lines.Add (floattostr(s));

 

(*перевод чисел в строку*)

Str(S:n:m,strl);

(*Вывод числа strl*)

form1.Memo1.Lines.Add(strl);

(*Приравнивание переменных к нулю*)

c:=0 ;b:=0;

(*Открытие цикла while*)

while c<=9 do begin

(*перевод чисел в строку*)

str(c,sr);

(*Открытие цикла for(счётчик), Функция length возвращает в качестве результата значение текущей длины строки-параметра *)

for i:=1 to length(strl) do

begin

 (* условие если strl[i] равно числу sr тогда к b+1, в противном случае возвращаемся циклу*)

          if strl[i]=sr then inc(b);

end;

 (* Выводим результат*)

form1.Memo1.Lines.Add('Число '+floattostr (c)+' в числе '+(strl)+' встречаеться '+floattostr(b)+' раз');

 

(*Прибавляем к переменной (С) 1,и приравниваем переменную  b к нулю, после чего возвращаемся в цикл while*)

inc(c);

b:=0;

end;

end;

(* Конец программы *)

end.        

 

 

 

 

 

 

 

 

 

 

 

 

 

6. Проверка работоспособности и доказательство правильности работы ПО.

Проведем тестирование данной системы на различные варианты:

1:

1. В числе М вводим число 5
2. В степени N вводим 2

     5 в степени  2=25

Количество повторений чисел 2=1;5=1

Результат работы системы:

2:

1. В числе М вводим число 35
2. В степени N вводим 5

     35 в степени 5= 52521875

Количество повторений чисел 1=1;2=1;3=0;4=0;5=3;8=1;

Результат работы системы:

3:

1. В числе М вводим число 48
2. В степени N вводим 95

     48 в степени 95= 5.2229702328614029E+0159

Количество повторений чисел 0=3;1=2;2=6;3=1;4=1;5=2;6=1;7=1;8=1;9=3;

Результат работы системы:

 

Приведенные выше примеры  доказывают правильность и работоспособность  данной программы.

 

 

 

 

 

7. Инструкция пользователя.

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

Setup.exe

Двойным нажатием на него левой  кнопки мыши или нажав правой кнопкой  мыши и выбрать появившегося меню «открыть».

После чего появившемся окне нужно выбрать язык «русский» или «английский».

После выбора языка нажмите  кнопку «ОК»

 

 

 

 

 

 

 

 

Следующем отрытом окне:

Нажимаем на кнопку «Далее»

После чего в появившемся  окне:

 выбираем путь установки  программы при помощи кнопки  «обзор» 

После нажимаем кнопку «Далее»

В след окне выбираем: нужен ли вам ярлык на рабочем столе.

- Нужен(С галочкой)

- Не нужен(Без галочки)

После соответствующего вам  выбора, нажимаем кнопку «Далее»

В появившемся окне вы можете проверить (каталог установки это  то место в компьютере, куда вы устанавливаете данную программу) и создали ли вы ярлык на рабочем столе или  же нет?

 

Если вы хотите что-то изменить нажмите кнопку «Назад»

Если всё в порядке  выберете кнопку «Установить»

После завершения процесса установки, появиться окно

В котором вы можете выбрать  запустить программу поставив галочку  перед «Запустить задачу на поиск схожих чисел», в противном случае галочку не ставим.

После вашего выбора нажимаем кнопку «Готово»

После чего запускаем программу  с ярлыка на рабочем столе или  же в нашем случае это запуск после  нажатие кнопки «Готово»

В появившемся окне:

Выбираем значения M и N:

После вашего выбора, нажимаем на кнопку «ответ»

После получения результата появившегося в правой стороне окна

Можете скопировать ответ: выделив ответ и нажав на нём  правой кнопкой мыши и появившемся  меню выбрать «копировать» нажав  левой кнопкой мыши.

После чего можете закрыть  программу, нажав на «закрыть»

Инструкция по удалению:

Для удаления программы зайдите  в меню «установка и удаление программ», Выберите программу (Сколько чисел1.00) и нажмите удалить.