Вградени числови типове
Всеки език за програмиране предлага числови типове на данните
• signed char - размер: 1 байт, обхват: -128 до 127.
• unsigned char - размер: 1 байт, обхват: 0 до 255
• short - размер: 2B, обхват: -32768 до 32767 със знак или 0 до 65535 без знак
• int - размер: 4B, обхват: -2147483648 до 2147483647 със знак или 0 до 4294967295 без знак
• long - размер: обикновено 4B, не се различава от int.
• long long - размер: 8B, обхват –9,223,372,036,854,775,808 до 9,223,372,036,854,775,807 със знак или 0 до 18,446,744,073,709,551,615 без знак.
• float - размер: 4B, обхват: 3.4e +/- 38, точност: 7 знака след десетичната запетая
• double - размер: 8B, обхват: 1.7e +/- 308, точност: 15 знака след десетичната запетая
Размерите на вградените типове могат да варират според архитектурата, операционната система и средата. Според размера се променя и обхвата на съответния тип.
Ако за програмата е жизнено значение размера на типа (например при динамично заделяне на памет) е препоръчително да се използва оператора sizeof(<тип>), който връща размера на подадения тип в байтове.
При използване типовете float, double и long double трябва да се внимава при използването на точността им. Понякога при деление например на числа (float), които са с 5-6 знака след десетичната запетая се наблюдават малки грешки в прецизността на операциите.
Често използвани алгоритми за работа с числа
• Пресмятане на НОД и НОК
• Делимост на числа
• Работа с прости числа – генериране на прости числа в интервала от 1 до N, генериране на прости числа в интервала от М до N, проверка за просто число, разлагане на число на прости множители
• Работа с големи числа
• Бързи алгоритми за извършване на някои аритметични действия
Алгоритми за намиране на НОД и НОК
Един от най-известни алгоритми за намирание на най-голям общ делител на две естествени числа е известен още от древността като Алгоритъм на Евклид.
Описание на алгоритъма. Нека имаме две естесвени числа a и b.
1) Ако b == 0, то a е НОД на числата a и b.
2) Ако b != 0, то a = b, b = a mod b и отивам на стъпка 1).
Алтернативи
Алгоритъмът на Евклид ефективен при малки числа. Съществуват по-сложни алгоритми, които са по-бързи и приложими за големи числа.
Един такъв е Binary GCD algorithm. Въпреки че също е със сложност О(n^2), при реални тестове се представя доста по добре от алгоритъма на Евклид. Той използва двоичното представяне на числата е компютъра, където е възможно деленията да се заместват с изместване, което е по-бърза операция.
Двоичен алгоритъм за намиране на НОД
Този алгоритъм редуцира намирането на НОД чрез прилагане на следните правила:
1. НОД(0, v) = v, тъй като 0 дели всичко, а v е най-голямото число, което дели v. аналогично, НОД(u, 0) = u. НОД(0, 0) е неопределен.
2. Ако u и v are са четни, НОД(u, v) = 2•НОД(u/2, v/2), тъй като 2 е общ делител.
3. Ако u е четно, а v е нечетно, тогава, НОД(u, v) = НОД(u/2, v), тъй като 2 не е обще делител. Аналогично, ако u е нечетно, а v е четно, НОД(u, v) = НОД(u, v/2).
4. Ако u и v са нечетни и u ≥ v, тогава НОД(u, v) = НОД((u−v)/2, v). Ако и двете са нечтни и u < u =" v," u =" 0.">
using namespace std;
#define LIMIT 100 //the range in which we will look for primes is 2*LIMIT
int main()
{
bool primes[LIMIT]; //bool array, marking the prime numbers, cell with number i marks number 2*i + 1
int i,j;
for (i=0; i < i="1;" j =" 3*i+1;" i="1;" end="" in="" array="" you="" will="" have="" the="" index="" of="" all="" primes="" from="" 3="" to="" as="" number="" 1="" return="" x="" define="" n="" 1000="" bool="" int="" i="0;"><= x; ++i ) if( x % primes[i] == 0) return false; return true; } void genPrimes() { primes[0]=2; int i=1; int x=3; while(i<= е <= 29. По-точно е е някое от числата 1, 7, 11, 13 взети със знак минус и плюс. Така значително намаляваме броя проверки. Можем да направим още подобрения, ако вместо три вземем повече прости числа. Хипотеза на Голдбах Хипотезата на Голдбах не е доказана, но може да бъде проверена до някаква определена стойност чрез прост алгоритъм. Формулировка - за всяко цяло четно число n>2, съществува поне една двойка прости числа a и с (не непременно различни) такива че a + c = n.
Решение: Първо използваме Решето на Ератостен и намираме всички прости числа от 1 до n. Резултата съхраняваме в булев масив primes, като с единица означаваме простите числа, а с 0 съставните. Ето го и решението:
int FindSol(int n)
{
int i,res=0;
for(i=2;i<=n/2;i++) if (primes[i] && primes[n-i]) res++; return res; } Свойства на простите числа • Всеки общ делител на a и b е делител на НОД(a, b). • НОД(a, b), където a или b не е нула, може да се дефинира еквивалентно по друг начин като най-малкото положително цяло число d, което може да се запише във формата d = a•p + b•q, където p и q са цели числа. Този израз се нарича тъждество на Безу. Числата p и q могат да се изчислят чрез разширения алгоритъм на Евклид. • Ако a е делител на произведението b•c, и НОД(a, b) = d, то a/d е делител на c. • За произволно цяло число m НОД(m•a, m•b) = m•gcd(a, b) и НОД(a + m•b, b) = gcd(a, b). Ако m е ненулев общ делител на a и b, то НОД(a/m, b/m) = gcd(a, b)/m. • НОД е мултипликативна функция в следния смисъл: ако a1 и a2 са взаимно прости, то НОД(a1•a2, b) = НОД(a1, b)•НОД(a2, b). • НОД на три числа може да се пресметне като НОД(a, b, c) = НОД(НОД(a, b), c) = НОД(a, gcd(b, c)). Следователно НОД е асоциативна операция. • НОД(a, b) е тясно свързано с най-малкото общо кратно НОК(a, b): в сила е НОД(a, b)•НОК(a, b) = a•b. Тази формула често се използва за пресмятане на общи кратни: първо се изчислява НОД по алгоритъма на Евклид и след това се дели произведението на зададените числа на техния НОД. Валидни са следните варианти на дистрибутивност: НОД(a, НОК(b, c)) = НОК(НОД(a, b), НОД(a, c)) НОК(a, НОД(b, c)) = НОД(НОК(a, b), НОК(a, c)). • Полезно е да се дефинира НОД(0, 0) = 0 и НОК(0, 0) = 0, защото тогава естествените числа стават пълна дистрибутивна решетка с НОД като инфимум и НОК като супремум операция. Това разширение на дефиницията е съвместимо и с обобщението за комутативни пръстени, дадено по-долу. • В декартова координатна система НОК(a, b) може да се интерпретира като броя точки с цели координати върху отсечката, свързваща началото(0, 0) и (a, b), без (0, 0). Работа с големи числа Обикновено работата с големи числа, се явява само като фрагмент от някоя задача - например ограниченията за входа са прекалено, за да се използват вградените типове. Затова, въпреки че рядко се срещат задачи които да представляват само и единствено работа с големи числа е важно да може да се работи с тях. Представяне Според случая може да се използват различни представяния за големи числа. Един такъв вариант е битово поле, в което числата да се съхраняват в двоичен вид. При този вариант се пести място, то работата със самите числа става по-трудна. Възможно е числата да се съхраняват и като низове. Тук загубата на място е значителна, тъй като за всяка цифра се използва 1B, а се използват 4-5 бита. За сметка на това, работата е значително по-лесна. При тези представяния елементарните операции като умножение и събиране се имплементират сравнително лесно като се използва естествения подход. Ако се добави поддръжка на отрицателни числа, изваждането се замества лесно със събиране. Друг, близък начин за представяне, е използването на масив от цели числа, като един елемент на масива представя една цифра е десетична или в система с по-висока основа. Доста често, обаче задачите изискват нещо повече от събиране и изваждане. Понеже отнема време да се реализира клас големи числа с всички необходими операции е удачно да се използва вградена библиотека. За съжаление в С++ няма такава. Бързо умножение Обикновения алгоритъм за умножение на две числа, който всички познаваме от училище, е крайно ефективен. В общия случай, неговата сложност е O(n^2). Толкова често го използваме че дори не се замисляме за неговата ефективност. Когато ни се налага сами да имплементираме е добре да имаме по-ефикасно решение. Ето един примерен алгоритъм. При него не е необходимо да знаем цялата таблица за умножение наизуст, а само умножение и деление с 2 и събиране. Този алгоритъм трансформира сложното умножение в няколко прости операции. Алгоритъм 1) направете таблица с три колони, в първата напишете първото число, а във втората - второто. Третата остава празна за сега. 2) започнете да делите първото число на две, като взимате само цялата част. Записвайте резултатите последователно в първата колонка докато не стигнете до 1. 3) умножете второто число по две, толкова пъти колкото сте разделили първото и отново записвайте резултатите последователно. 4) в третата колонка прехвърлете всички резултати от втората колонка, които стоят до нечетно число от първата колона. 5) съберете числата от третата колона и това е вашия резултат. Пример: 455*259 455 259 259 227 518 518 113 1036 1036 56 2072 28 4144 14 8288 7 16576 16576 3 33152 33152 1 66304 66304 Резултат: 117845 Този алгоритъм е доста удобен за интерпретиране при работа с двоична бройна система, понеже умноженията и деленията на две се заместват от изместване на ляво и дясно (доста бързи операции). Подходящ е за имплементация при работа с големи числа.