Въпросник по “Информатика” редовно обучение във ВСИ I курс
ВЪПРОСНИК
за изпит по ПРОГРАМИРАНЕ,
специалност „Бизнес информационни технологии“, редовно, I курс
61, 62, 64, 66, 68, 70, 71, 77, 80, 73, 82 Посочете алтернативна на основната теорема формулировка за единственост на представянето на естествените числа в ПБС, при отказ от представяне на всички естествени числа. представянето на N е единствено anan-1…a1a0 (p)
Какво е най-важното следствие от основната теорема на ПБС? представянето на N е единствено anan-1…a1a0 (p)
Еднозначен ли е записът на произволно цяло число в ПБС с дадена основа? да
Еднозначен ли е записът на произволно цяло число в НПБС? не
Алгоритмическо число може да се запише по няколко начина (липса на еднозначност).
Колко ПБС могат да съществуват и по какво се различават те? Безброй много. Различават се по основата и по възловите числа.
Колко алгоритъма за получаване на записа на дадено естествено число в ПБС с основа q съществуват, когато познаваме неговия запис в ПБС с основа p? По какво се различават тези алгоритми?
Задачата има 2 решения в зависимост от това, в коя от двете ПБС умеем да извършваме пресмятания.
1. Пресмятания в приемашата основа Q
Цифрите на ai на p–ичната БС и нейната основа p са числа ai‘ и p’, в q–ична БС. Заменяме тези цифри и основата със съответните числа и извършваме пресмятания в БС с основа q:
N=anan-1Ka1a0=anpn+an-1pn-1+K+a1p+a0=a’np’n+a’n-1p’n-1+K+a’1p+a’0=K
Изчисленията са по-прости по схемата на Хорнер за изчисляване на стойностите на полином:
(K ((a’np’ + a’n-1)p’+ a’n-2) p’+K+ a’1) p’+ a’0
Пример: преобразуване от (каква да е) в (10)
2. Пресмятания в изходната отснова p
Търсим m и bi за да представим N във вида:
N=bmqm+bm-1qm-1+K+b1q+b0 Делим N на q като изчисляваме частно и остатък от делението:
N= bmqm+bm-1qm-1+K+b1q+b0 = b0 qqq
Пример: От (10) в (каква да е)
3. Частен случай 1
Едната основа е точна степен на другата, например q=pk. Тогава:
0<=ai+k-1pk-1+…+ai+1p+ai<=pk-1=q-1
цифра при основа q
т.е к-цифрена поредица при основа p се заменя с една цифра при основа q и обратно:
ai+k-1…ai+1ai = bsДостатъчно е предварително да съставим таблица на подобни замени. (преобр. от (8) в (2).
4. Частен случай 2
Двете основи са точна степен на трето число, например p=sr, q=st. Естествено е да използваме като посредник основа s. Преимер (16=24) в (8=23)
Кои аритметични операции са в основата на всеки от двата алгоритъма за преобразуване на записа на естествено число от ПБС с една основа в ПБС с друга основа? Коя операция при кой алгоритъм се използва?
1. Събираме, умножение. 2.Събиране, умнож., деление.
