Cheksiz sig’imdagi integer muammosi
Muammo: Cheksiz sig’imdagi integerlar ustida qo’shish, ayirish, bo’lish, ko’paytirish va daraja amallarini bajarish.
.Netda BigInteger mavjud bo’lib, ushbu ma’lumotlar tipida taxminan 232 dan 264 gacha raqamdan iborat bo’lgan sonni saqlashingiz mumkin. Bu esa cheksiz degani emas. Cheksiz bu judayam nisbiy tushuncha shu sabab 264 dan ko’proq raqamdan tashkil topgan sonlar haqida gaplashamiz. Bu muommoning yechimi uchun DoubleLinkedListdan foydalanamiz. Har bir node int lardan tashkil topgan bo’ladi.
UnlimIntegerLinkedList classning konstruktori yordamida string ko’rinishida berilgan sonni DoubleLinkedListga o’girib olamiz.
public UnlimIntegerLinkedList(string number)
{
foreach (char ch in number)
{
AddLast(int.Parse(ch.ToString()));
}
}
Qo’shish amali. Qo’shish amali qanday bajaralishi hammaga ma’lum ikki son tegma-teg yozib olinadi va xonama — xona qo’shib boriladi. Xuddi shu usulni biz ham qo’lladik. Har ikkala DoubleLikedListning dumidan boshlab boshiga qadar raqamlarni qo’shib borib, yakunda kerakli yangi DoubleLinkedListni hosil qilamiz.
public UnlimIntegerLinkedList Add(UnlimIntegerLinkedList linkedList)
{
// agar qo'shiluvchi son null bo'lsa u holda natija 0 ga teng bo'ladi.
if (linkedList == null || linkedList.Head == null)
{
linkedList = new UnlimIntegerLinkedList("0");
}
//qo'shilma LinkedListning boshi null bo'lsa son 0ga teng
if (Head == null)
{
AddFirst(0);
}
// yig'indi uchun o'zgaruvchi
UnlimIntegerLinkedList result = new UnlimIntegerLinkedList();
//qo'shilmaning oxirgi xonasidan boshlab birinchi xonasiga qarab boramiz
DoubleLinkedListNode current1 = Tail;
//qo'shiluvchi uchun kursor
DoubleLinkedListNode current2 = linkedList.Tail;
//xonaning yigindisi o'ndan oshgan taqdirda
//yodda saqlanadigan son
int remainder = 0;
//toki har ikkala raqamni xonalarini yurib chiqmagunimzcha davom etadi.
while (current1 != null || current2 != null)
{
//qo'shilmaning xonalari uchun o'zgaruvchi
//qo'shilmaning xonalari tugagan taqdirda 0 ga deb olamiz.
int value1 = 0;
if (current1 != null)
value1 = current1.Value;
//qo'shiluvchining xonalari uchun o'zgaruvchi
//qo'shiluvchining xonalari tugagan taqdirda 0 ga deb olamiz.
int value2 = 0;
if (current2 != null)
value2 = current2.Value;
//mos xonalar va oldin yig'indidan yodda saqlanga sonlarning yig'indisi
value1 += value2 + remainder;
//agar 10ga teng yoki katta bo'lsa
if (value1 >= 10)
{
// 1 ni yodda saqlaymiz
remainder = 1;
//xonalar yi'gindisi
value1 %= 10;
}
else
{
// agar yig'indi 10dan kichik bo'lsa
remainder = 0;
}
//yig'indi natijaning oxiridan boshlab raqam qo'yib boramiz.
result.AddFirst(value1);
//qo'shilmaning bitta oldingi xonasi
current1 = Prev(this, current1);
//qo'shiluvchining bitta oldingi xonasi
current2 = Prev(linkedList, current2);
}
//agar yodda saqlangan son 0ga teng bo'masa sonning boshiga qo'shamiz.
if (remainder != 0)
result.AddFirst(remainder);
return result;
}
// qo'shish test
private static void Main(string[] args)
{
Console.WriteLine("BigInteger yordamida:" + BigInteger.Add(97646273472346, 97646273472346));
UnlimIntegerLinkedList one = new UnlimIntegerLinkedList("97646273472346");
UnlimIntegerLinkedList two = new UnlimIntegerLinkedList("97646273472346");
DateTime start = DateTime.Now;
one = one.Add(two);
TimeSpan t = DateTime.Now - start;
Console.WriteLine("Natija:");
one.Print();
Console.WriteLine("----------------");
Console.WriteLine("Sarflangan vaqt(MilliSekund): " + t.Milliseconds);
Console.WriteLine("Natija raqamlar soni: " + one.Count);
Console.WriteLine("Qoshimcha misol: ");
one = new UnlimIntegerLinkedList("97646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346");
two = new UnlimIntegerLinkedList("97646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346");
start = DateTime.Now;
one = one.Add(two);
t = DateTime.Now - start;
Console.WriteLine("Natija:");
one.Print();
Console.WriteLine("----------------");
Console.WriteLine("Sarflangan vaqt(MilliSekund): " + t.Milliseconds);
Console.WriteLine("Natija raqamlar soni: " + one.Count);
}
Ayirish amali. Yig’indini hisoblash singari sonning oxirgi raqamidan birinchi raqami tomonga siljib boramiz. Agar ayirma ayiriluvchidan kichik bo’lsa qo’shni xonadan 1 ni qarzga olib turamiz. Soddalik maqsadida musbat sonlar bilan ishlaymiz.
public UnlimIntegerLinkedList Subtract(UnlimIntegerLinkedList linkedList)
{
//natija manfiy son bo'lsa xayrlashamiz.
if (CompareTo(linkedList) == 2)
{
Console.WriteLine("Manfiy sonlar bilan ishlamayman! Qaytadan urining.");
return null;
}
//natija
UnlimIntegerLinkedList result = new UnlimIntegerLinkedList();
//ayirma uchun kursor
DoubleLinkedListNode current1 = Tail;
//ayiriluvchi uchun kursor
DoubleLinkedListNode current2 = linkedList.Tail;
//qarzga olingan 1
int remainder = 0;
//har ikki sonning barcha xonalarini ko'rib chiqamiz.
while (current1 != null || current2 != null)
{
//ayirmaning raqamlari uchun
//agar ayirmaning xonalari tugab qolsa 0 deb olamiz.
int value1 = 0;
if (current1 != null)
value1 = current1.Value;
//ayiriluvchining raqamlari uchun
int value2 = 0;
if (current2 != null)
value2 = current2.Value;
//qarzga olingan son uchun, agar qarz olinmagan bo'lsa 0ga teng
value2 += remainder;
//agar ayirmaning raqami ayiriluvchining xonasidan kichik bo'lsa
//qo'shnidan qarz so'raymiz
if (value1
Ko'paytirish amali. Ko'paytirish uchun sonning pozitision notatsiya ifodasidan foydalanamiz.
Ya'ni raqamlarni 10 liklarda ifodalab olib ko'paytmani yig'indisini hisoblaymiz.
public UnlimIntegerLinkedList Multiply(UnlimIntegerLinkedList linked)
{
UnlimIntegerLinkedList result = new UnlimIntegerLinkedList();
//sonlardan birorta null ga teng bo'lsa natija 0ga teng.
if (linked.Head == null || Head.Value == 0 || linked.Head.Value == 0)
return result;
DoubleLinkedListNode current;
//agar ko'payuvchi bitta raqamdan iborat bo'lsa
if (Head == Tail)
{
//ko'paytiruvchining raqamlarini birma-bir ko'paytirib chiqamiz.
current = linked.Tail;
//ko'paytma 10dan yuqori bo'lgan taqdirda yodda saqalanadigan son
int remainder = 0;
//ko'paytiruvchining barcha raqamlarini ko'rib chiqamiz
while (current != null)
{
//raqamlar ko'paytmasi
int value = Head.Value * current.Value;
//oldingi xonadan ortib qolgan sonni qo'shamiz
value += remainder;
//agar ko'paytma 10ga teng yoki katta bo'lsa
if (value >= 10)
{
//yodda saqlaymiz
remainder = value / 10;
//qoldiqni raqamga o'zlashtiramiz
value %= 10;
}
else
{
//aks holda yodda saqlanga son 0 ga teng
remainder = 0;
}
//natijani boshidan qo'shib boramiz
result.AddFirst(value);
//ko'paytiruvchining oldingi xonasi
current = Prev(linked, current);
}
if (remainder != 0)
{
result.AddFirst(remainder);
}
}
else
{
//ko'payuvchini bir xonali holatga kelirib olamiz
current = Head;
result.AddFirst(0);
//buning uchun 10 xonaliklarni sanab olib
//bizning misolda zeros ning elementlari soni 3ga teng
UnlimIntegerLinkedList zeros = new UnlimIntegerLinkedList();
for (int i = 0; i 54=>54000
//3*54=>162=>16200
//4*54=>2160
//5*54=>270
if (zeros.Count > 0 && tempResult.Count > 0)
tempResult.Merge(zeros);
//hosil bo'lgan sonlarni qo'shib chiqamiz
//54000+16200+2160+270
result = result.Add(tempResult);
//keyingi xona
current = current.Next;
//10liklarning oxiridan bitta o'chiramiz
//ya'ni 1000->100->10->1
zeros.RemoveLast();
}
}
return result;
}
//ko'paytirish amali test
private static void Main(string[] args)
{
Console.WriteLine("BigInteger yordamida:" + BigInteger.Multiply(97646273472346, 9764627347234));
UnlimIntegerLinkedList one = new UnlimIntegerLinkedList("97646273472346");
UnlimIntegerLinkedList two = new UnlimIntegerLinkedList("9764627347234");
DateTime start = DateTime.Now;
one = one.Multiply(two);
TimeSpan t = DateTime.Now - start;
Console.WriteLine("Natija:");
one.Print();
Console.WriteLine("----------------");
Console.WriteLine("Sarflangan vaqt(MilliSekund): " + t.Milliseconds);
Console.WriteLine("Natija raqamlar soni: " + one.Count);
Console.WriteLine("Qoshimcha misol: ");
one = new UnlimIntegerLinkedList("97646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346");
two = new UnlimIntegerLinkedList("9764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346976462734723469764627347234697646273472346");
start = DateTime.Now;
one = one.Multiply(two);
t = DateTime.Now - start;
Console.WriteLine("Natija:");
one.Print();
Console.WriteLine("----------------");
Console.WriteLine("Sarflangan vaqt(MilliSekund): " + t.Milliseconds);
Console.WriteLine("Natija raqamlar soni: " + one.Count);
}
Bo'lish amali. Man uchun muammoning eng qiziq qismi bo'ldi. Bo'linmani ayirmalar yordamida ifodalab olishimiz mumkin.
Misoldan ko'rinib turganidek, 34 marta ayirgandan ko'ra 7 marta ayirish tezroq.
public UnlimIntegerLinkedList Divide(UnlimIntegerLinkedList linked)
{
//agar bo'luvchi bo'linuvchidan katta bo'lsa natija 0
if (CompareTo(linked) == 2)
{
return new UnlimIntegerLinkedList("0");
}
//agar bo'luvchi va bo'linuvchi teng bo'sa natija 1
if (CompareTo(linked) == 1)
return new UnlimIntegerLinkedList("1");
//bo'linma
UnlimIntegerLinkedList result = new UnlimIntegerLinkedList("0");
//bo'linuvchining
UnlimIntegerLinkedList temp = this;
//ayirlarning darajasini hisoblab borish uchun
//766-2 * 23 = 720
//720-4 * 23 = 628
//628-8 * 23 = 444 ifodalardagi 2,4,8 lar.
UnlimIntegerLinkedList quotient = new UnlimIntegerLinkedList("1");
//bo'luvchi
UnlimIntegerLinkedList divider = linked;
//bo'linuvchi bo'luvchidan kichik bo'lib qolguncha davom etadi
int comparision = temp.CompareTo(linked);
while (comparision
Daraja amali. Oldingi maqolamizdan muhokama qilingan usuldan foydalanamiz. Quyidagi kod parchasiga e'tibor bering.
public UnlimIntegerLinkedList Pow(int n)
{
//rekursiyaning to'xtash nuqtasi
if (n == 0)
return new UnlimIntegerLinkedList("1");
//rekursiyaning to'xtash nuqtasi
if (n == 1)
return this;
//agar darajas juft bo'lsa
if ((n & 1) == 0)
return Multiply(this).Pow(n / 2);
//daraja toq bo'lsa
return Multiply(Multiply(this).Pow((n - 1) / 2));
}
private static void Main(string[] args)
{
Console.WriteLine("BigInteger yordamida:" + BigInteger.Pow(97646273472346, 40));
UnlimIntegerLinkedList one = new UnlimIntegerLinkedList("97646273472346");
DateTime start = DateTime.Now;
one = one.Pow(40);
TimeSpan t = DateTime.Now - start;
Console.WriteLine("Natija:");
one.Print();
Console.WriteLine("----------------");
Console.WriteLine("Sarflangan vaqt(MilliSekund): " + t.Milliseconds);
Console.WriteLine("Natija raqamlar soni: " + one.Count);
Console.WriteLine("Qoshimcha misol: ");
one = new UnlimIntegerLinkedList("678989745743958273459827345984237");
start = DateTime.Now;
one = one.Pow(400);
t = DateTime.Now - start;
Console.WriteLine("Natija:");
one.Print();
Console.WriteLine("----------------");
Console.WriteLine("Sarflangan vaqt(MilliSekund): " + t.Milliseconds);
Console.WriteLine("Natija raqamlar soni: " + one.Count);
}
Bir narsani ta'kidlamoqchimiz, maqsadimiz eng tez yoki eng optimal usulni taklif qilish emas, maqsadimiz iloji borligini ko'rsatish. Optimal usul natija uchun, darajani hisoblashning boshqa usullariga chuqurroq sho'ng'ish kerak. Undan tashqari ko'paytirish amalini ham optimallashtirish lozim.
Asosiy koddan tashqari taqqaslash, bitta oldingi xonani topsih, ekranga chiqarish kabi amallar uchun metodlar mavjud. Ushbu blogda muhokama qilingan DoubleLinkedList ustiga qurilgan.
Manba:
Algoritm
Cheksiz sig’imdagi integer muammosi