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]);

}

}

}

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


 

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

34589. ОСНОВНЫЕ ФАКТОРЫ РОССИЙСКОГО ИСТОРИЧЕСКОГО ПРОЦЕССА 19.56 KB
  Самобытность России во многом определяется ее географическим положением между Европой и Азией – миром модернизации и миром традиционности. Этот фактор накладывает отпечаток на историческое развитие России. В самой России начиная с XVIII в. Главным среди природных факторов был континентальный характер расположения территории России.
34590. МЕСТО РОССИИ СРЕДИ МИРОВЫХ ЦИВИЛИЗАЦИЙ 24 KB
  МЕСТО РОССИИ СРЕДИ МИРОВЫХ ЦИВИЛИЗАЦИЙ Составитель: С. Соответственно и место России во всемирной истории определялось с точки зрения принадлежности ее к одной из общественноэкономических формаций.К какому же типу отнести Россию В какой мере самобытна цивилизация России Ответы на эти вопросы давались историками публицистами общественными деятелями с высоты своего времени с учетом всего предшествующего развития России а также в соответствии со своими идейнополитическими установками. Абсолютное большинство населения России исповедует...
34591. ВОСТОЧНЫЕ СЛАВЯНЕ В ДОФЕОДАЛЬНЫЙ ПЕРИОД 22.91 KB
  ВОСТОЧНЫЕ СЛАВЯНЕ В ДОФЕОДАЛЬНЫЙ ПЕРИОД Составитель: Л. Степанова Появление славян как самостоятельного этноса согласно археологическим материалам произошло еще в первое тысячелетие до н. славяне известны под именем антов и венедов. в источниках появляется имя славяне.
34592. ДРЕВНЕРУССКОЕ ГОСУДАРСТВО: ЗАКОНОМЕРНОСТИ И ОСОБЕННОСТИ ОБРАЗОВАНИЯ, СОЦИАЛЬНЫЙ И ПОЛИТИЧЕСКИЙ СТРОЙ (IX – начало XII вв.) 21.55 KB
  Но произошло это объединение в результате похода князя Олега датируемого летописью 882 годом при активном участии его Руси – варяжской дружины вместе с другими племенами Поильменья. Рассматривая особенности политического устройства Киевской Руси следует выделить такой родоплеменной пережиток как наследование великого княжения по старшинству. Это заставляло всю многочисленную родню Рюриковичей время от времени менять свое пребывание в одном из княжеств и перебираться в другое что не способствовало ни укреплению центральной власти в Киеве...
34593. США во Второй мировой войне 14.25 KB
  Когда УВП не удалось взять под свой контроль добычу и поставки сырья Рузвельт создал сначала управление экономической стабилизации а затем управление военной мобилизации наделенное чуть ли не диктаторскими полномочиями. Комиссия по справедливому найму которую Рузвельт был вынужден создать под угрозой негритянского марша на Вашингтон во главе с Филипом Рэндолфом председателем профсоюза железнодорожных проводников помогла афроамериканцам бороться с дискриминацией в военной промышленности особенно после того как в 1943 Рузвельт наделил...
34594. США в конце XX – начале XXI вв 15.84 KB
  Укрепление политического экономического военного лидерства в мире стало ведущей идеей политики США во второй половине XX начале XXI в. Этому способствовало с одной стороны ключевое положение США в ООН в составе 5 государств членов Совета Безопасности а с другой активное участие в создании НАТО сети других военнополитических блоков. Была развернута сеть военных баз и объектов США в Европе в государствах участниках НАТО на Дальнем Востоке и в бассейне Тихого океана в Латинской Америке и зоне Карибского бассейна на Ближнем...
34595. Соединенное Королевство: географическое положение, рельеф, природные условия, флора и фауна. Символы 40.5 KB
  Официально же она именуется Соединенное Королевство Великобритании и Северной Ирландии. В целом на их долю приходится приблизительно 1 3 площади Великобритании и бoльшая часть Северной Ирландии. В Северной Ирландии змей нет. Символы: Флаг Соединенного Королевства Великобритании и Северной Ирландии или как его принято называть Юнион Джек Union Jck является сочетанием трех крестов святых покровителей Англии прямой красный крест на белом поле крест Св.
34596. Столетняя война 17.15 KB
  Столетняя война наименование длительного военного конфликта между Англией и Францией 13371453 вызванного стремлением Англии вернуть принадлежавшие ей на континенте Нормандию Мен Анжу и др. а также династическими притязаниями английских королей на французский престол. война между Англией и Францией. причины войны: стремление Франции вытеснить Англию с югозапада страны провинция Гиень и ликвидировать этот последний оплот английской власти на франц.
34597. Династия Тюдоров. Генрих VII 19.17 KB
  Генрих VII Генрих VII Тюдор 28 января 1457 – 21 апреля 1509 – король Англии и государь Ирландии 1485 – 1509. Родители: Эдмунд Тюдор 1й граф Ричмонд; единоутробный брак короля Генриха VI Маргарита Бофорт. 1471 – гибель Генриха VI и принца Уэльского Генрих – почти единственный родственник Ланкастеров. Генрих поклялся в Ренне в случае захвата власти жениться на дочери Эдуарда IV Елизавете Йоркской.