3572

Алгоритми роботи з цілими числами

Лекция

Информатика, кибернетика и программирование

Тип ціле число є основним для будь-якої алгоритмічної мови. Зв'язано це з тим, що вміст комірки пам'яті або регістра процесора можна розглядати як ціле число. Адреси елементів пам'яті також являють собою цілі числа, з їхньою допомогою записуються машинні команди й т.д...

Украинкский

2012-11-03

54 KB

3 чел.

Алгоритми роботи з цілими числами

Тип ціле число є основним для будь-якої алгоритмічної мови. Зв'язано це з тим, що вміст комірки пам'яті або регістра процесора можна розглядати як ціле число. Адреси елементів пам'яті також являють собою цілі числа, з їхньою допомогою записуються машинні команди й т.д. Символи представляються в комп'ютері цілими числами - їхніми кодами в деякому кодуванні. Зображення також задаються масивами цілих чисел: для кожної крапки кольорового зображення зберігаються інтенсивності її червоної, зеленої й синьої складової (у більшості випадків - у діапазоні від 0 до 255). Як говорять математики, цілі числа дані, а все інше сконструювала з них людина.

Загальноприйнятий у програмуванні термін ціле число або ціла змінна, строго говорячи, не цілком коректний. Цілих чисел нескінченно багато, десятковий або двійковий запис цілого числа може бути як завгодно довгий й не міститися в області пам'яті, відведеної під одну змінну. Ціла змінна в комп'ютері може зберігати лише обмежену безліч цілих чисел у деякому інтервалі. У сучасних комп'ютерах під цілу змінну виділяється 8 байт, тобто 64 двійкового розряду. Вона може зберігати числа від нуля до 2 в 64-й ступені мінус 1. Таким чином, максимальне ціле число, що може зберігатися в цілій змінній, дорівнює

264 - 1 = 18,446,744,073,709,551,615

Арифметичні цілочисельні типи

Ім'я типу

Системний тип

Діапазон

Розмір

Sbyte

System.SByte

- 128... …127

Знакове, 8 Біт

Byte

System.Byte

0... …255

Беззнакове, 8 Біт

Short

System.Short

- 32768 …32767

Знакове, 16 Біт

Ushort

System.UShort

0... …65535

Беззнакове, 16 Біт

Int

System.Int32

- 2,147,483,648…2,147,483,647

Знакове, 32 Біт

Uint

System.UInt32

0...4…4,294,967,295)

Беззнакове, 32 Біт

Long

System.Int64

- 9,223,372,036,854,775,808 …

9,223,372,036,854,775,807

Знакове, 64 Біт

Ulong

System.UInt64

0...18…18,446,744,073,709,551,615

Беззнакове, 64 Біт

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

a+b = b+a, ab = ba

(a+b) + c = a+(b+c), (ab)c = a(bc)

a(b+c) = ab+ac

В елементарній шкільній математиці результат операції залишку від ділення традиційно вважається невід’ємним. Операція знаходження залишку буде позначатися знаком відсотка %, як у мові С#. Тоді, приміром,

3%5 = 3,

17%5 = 2,

(-3)%5 = 2,

(-17)%5 = 3.

Звідси видно, що в шкільній математиці не виконується рівність

(-a)%b = -(a%b),

Операції зміни знака й знаходження залишку не перестановочні ( математичною мовою, не комутирують один з одним). У комп'ютері операція знаходження залишку від ділення для від’ємних чисел визначається інакше, її результат може бути від’ємним. У наведених прикладах результати будуть наступними:

3%5 = 3,

17%5 = 2,

(-3)%5 = -3,

(-17)%5 = -2.

При діленні на позитивне число знак залишку збігається зі знаком діленого. При такому визначенні тотожність

(-a)%b = a%(-b) = -(a%b) справедлива.

Це дозволяє в багатьох алгоритмах не стежити за знаками (так само, як у тригонометрії формули, виведені для кутів, менших 90 градусів, автоматично виявляються справедливими для будь-яких кутів).

У двійковому поданні старший розряд у від’ємних цілих чисел дорівнює одиниці, у додатних - нулю. Двійкові розряди подання цілого числа в програмуванні нумерують від 0 до 31 справа наліво. Старший розряд має номер 31 і часто називається знаковим розрядом. Таким чином, знаковий розряд дорівнює одиниці у всіх від’ємних чисел і нулю в додатних. Двійкове подання максимального по абсолютній величині від’ємних чисел k складається з одиниці й тридцяти одного нуля:

-214748364810 = 100000000000000000000000000000002

Двійкове подання числа -1 складається із тридцяти двох одиниць:

-110 = 111111111111111111111111111111112

Двійкове подання максимального додатного числа складається з нуля в знаковому розряді й тридцяти однієї одиниці:

214748364710 = 011111111111111111111111111111112

Слід зазначити, що в програмуванні часто використовують також короткі цілі числа, двійковий запис яких займає вісім розрядів, тобто один байт, або шістнадцять розрядів, тобто два байти. Робота з такими короткими цілими числами підтримується на апаратному рівні. У мові Сі однобайтовим цілим числам відповідає тип Sbyte, двухбайтовим - тип short. Однобайтові цілі числа - це елементи кільця відрахувань Zm, де m = 28 = 256.

У випадку двухбайтових цілих чисел (тип short) m = 216 = 65536.

Розглянемо наступні алгоритми:

Лістинг 9.1. Дано ціле число , знайти суму і кількість чисел

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace ConsoleApplication1

{

class Program

{

static void Main(string[] args)

{

Console.WriteLine("Введите число: ");

int s = int.Parse(Console.ReadLine());

int i = 0, sum = 0; ;

while (s > 0)

{

int d = s % 10;

sum = sum + d;

s = s / 10;

i++;

 

}

Console.WriteLine("Сумма чисел = " + sum+ " kol"+i);

}

}

}

Лістинг 9.2. Знайти цифру , яка находиться на третьому місці введеного числа.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace ConsoleApplication2

{

class Program

{

static void Main(string[] args)

{

Console.WriteLine("Введите число: ");

int s = int.Parse(Console.ReadLine());

int i = 0, s1 = s;

while (s > 0)

{

s = s / 10;

i++;

}

s = s1; int l = 0;

while (s > 0)

{

int d = s % 10;

s = s / 10;

l++;

if (l==i-2) Console.WriteLine("число = " + d);

}

}

}

}

Спробуйте проаналізувати представлені алгоритми з представленням цілого числа типом string.

Лістинг 9.3.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace _25

{

class Program

{

static void Main(string[] args)

{

Console.WriteLine("Введите число: ");

string s = Console.ReadLine();

int i = 0, sum = 0; ;

string d;

for (i = 0; i < s.Length; i++)

{

d = null;

d += s[i];

sum += Int32.Parse(d);

}

Console.WriteLine("Сумма чисел = "+sum);

}

}

}

Лістинг 9.4.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace _26

{

class Program

{

static void Main(string[] args)

{

Console.WriteLine("Введіть число: ");

string s = Console.ReadLine();

Console.WriteLine("На третьому місці цифра " + s[2]);

}

}

}

Проаналізуйте наведені задачі, перевірте їх працездатність в середовищі програмування.


 

А также другие работы, которые могут Вас заинтересовать

49624. Розрахунки ділянки тепловозною тягою за одним варіантом ведення поїзда 1.57 MB
  Тяга поїздів – це галузева наука яка вивчає керований рух поїздів тобто такий рух що дозволяє досягти поставленої перед залізничним транспортом мети – повного та своєчасного забезпечення народного господарства у перевезеннях при безпеці цих перевезень та надійній роботі локомотивів. Таблиця 51 № елемента Довжина елемента Крутість Початкова швидкість Питома рівнодійна сила Відрізок шляху Швидкість кінцев...
49625. ДИСКРЕТНАЯ ОБРАБОТКА СИГНАЛОВ И ЦИФРОВАЯ ФИЛЬТРАЦИЯ 913.5 KB
  Дискретная обработка аналогового сигнала.1 Сравнить форму спектра дискретизированной последовательности со спектром исходного аналогового сигнала. Установить связь между: результатом Z – преобразования и спектральной плотностью дискретной последовательности; спектром исходного периодического аналогового сигнала и дискретными отсчетами его спектральной плотности.1 Методом билинейного Zпреобразования синтезировать цифровой фильтр нижних частот ФНЧ с частотой среза равной ширине основного лепестка в области положительных частот спектра...
49626. Разработка микропроцессорной системы с заданой частоты сигнала Fmax=200 Гц 806 KB
  Метки Оператор команды Операнд команды Комментарий MVI 36H Запись слова управления в регистр управления таймера OUT 7H MVI E8H Запись числа N в 0й канал OUT 4H MVI 3H OUT 4H MVI 72H Запись слова управления в регистр управления таймера OUT 7H CYCLE: MVI 8H Запись числа N в 1й канал OUT 5H MVI 52H OUT 5H MVI 1H Запуск таймера OUT 8H CC: IN 10H Опрос логического состояния счетного триггера JNZ CC MVI 0H Остановка таймера OUT 8H IN 5H Считывание частоты MOV C IN 5H MOV B MVI 8H Подсчет частоты SUB C MOV E MVI 52H...
49627. АНАЛИЗ ДЕНЕЖНЫХ ПОТОКОВ БАНКА (на материалах ПАО «ПриватБанк») 493.5 KB
  Осуществление практически всех видов финансовых операций коммерческого банка генерирует определенное движение денежных средств в форме их поступления или расходования. Это движение денежных средств функционирующего предприятия во времени представляет собой непрерывный процесс и определяется понятием “денежный поток”.
49628. ПРОЕКТ КОМПЬЮТЕРНОГО КЛАССА КОЛЛЕДЖА НА ОСНОВЕ БЕСПРОВОДНОЙ СЕТИ 143 KB
  Тема КР Организация локально-вычислительной сети учебного центра. Обеспечить выход в Интернет электронную почту а также: предусмотреть возможность развития сети за счет увеличения количества компьютеров в классах 1 и 2; обеспечить возможность обмена информацией между преподавателями; организовать резервирование данных; обеспечить возможность вывода на принтер D всем преподавателям а на принтер А и В только из кабинетов А и В соответственно. Перечень графического материала – схема сети.
49630. Привод к ленточному конвейеру с графиком нагрузки 2.63 MB
  Схема привода ленточного конвейера Окружное усилие на барабане Ft = 3 кН окружная скорость барабана V = 01 м с и диаметр барабана D = 350 мм. Коэффициент диаметра червяка: принимаем q = 125. Истинное межосевое расстояние Размеры червяка и колеса: Червяк: Делительный диаметр d1 = q ∙ m = 125 ∙ 5 = 625 мм. Диаметр вершин витков dа1 = d1 2 ∙ m = 625 2 ∙ 5 = 725 мм.
49631. Разработка комплекта технологической документации обработки детали на металлорежущих станках 142.6 KB
  В данной работе произведен анализ конструкции детали на технологичность выбор заготовки определен тип производства последовательность технологических операций рассчитаны оптимальные припуски на механическую обработку выбрано оборудование режущий и измерительный инструмент выбраны приспособления. Содержание Введение 4 1 Назначение и конструкция детали 5 2 Анализ конструкции детали на технологичность 7 3 Определение типа производства 8 4 Выбор заготовки 9 5 Техникоэкономическое обоснование выбора заготовки 10 5. 4 Выбор...