Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8824

Jo'natishlar soni: 714631

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1177


So'ngi izohlar

                  Kengaytirilgan Evklid algoritmi

 

Aslida oddiy Evklid algoritmi sizga yaxshi malumki ikkita sonning EKUBini topishda ishlatiladi. Keygaytirilgan Evklid algoritmi esa

a \cdot x + b \cdot y = {\rm gcd} (a, b).

tipdagi tenglamaning koeffisentlarini topishda qo’llaniladi.Bunda a va b koeffisentlarning EKUBidan foydalanamiz

 

                                              Algoritm   

 

Bu koeffisentlarni  Evklid algoritmi yordamida topish unchalik qiyin emas.Buning uchun a va b koeffisentlarni b%a va a ga almashtirish kifoya.

Keyin biz yangi b%a va a juftlik uchun x1 va y1 koeffisentlarni topdik deb hisoblaylik.

 

 (b \% a) \cdot x_1 + a \cdot y_1 = g,

Va biz a va b koefffisent uchun x va y ni topishimiz kerak.

Buning uchun b%a ni aniqlab olamiz

 b \% a = b - \left\lfloor \frac{b}{a} \right\rflo[...]

va uni x1 va y1 li ko’paytmaga qo’yamiz

 

 g = (b \% a) \cdot x_1 + a \cdot y_1 = \left( b -[...]

va ko’paytuvchilarni guruhlaymiz

 

 g = b \cdot x_1 + a \cdot \left( y_1 - \left\lflo[...]

Bu chiqqan ko’paytmani x va y koeffisentli bilan tenglaymiz va bizga kerakli javobni olamiz

 

 \cases{

x = y_1 - \left\lfloor \frac{b}{a} \righ[...]

                                                        Realizatsiya

 

static int xg,yg;

private static int gcd(int a, int b) {

       if (a == 0) {

          xg = 0; yg = 1;

            return b;

            }

      int d = gcd (b%a, a);

      int t = xg;

      xg = yg - (b / a) * xg;

      yg = t;

      return d;

          }

Ushbu rekursiv funksiya a va b larning EKUBini qaytarishdan tashqari ularning koeffisenti bo’lgan x va y ni ham hisoblaydi.

Rekursiya bazasi  a=0 bo’lgan holatdir.Bu holatda malumki EKUB b ga bizga zarur bo’lgan x va y koeffisentlar esa mos ravishda 0 va 1 ga teng bo’ladi.Boshqa holatlarda esa javob odatdagidek bo’lib koeffisentlar yuqoridagi formuladan topiladi.

Kengaytirilgan Evklid algoritmi bunday realizatsiya bilan hatto manfiy sonlar uchun ham to’g’ri ishlaydi.

Ikki o‘zgaruvchili chiziqli Diofant tenglamalar

 Ikki nomalumli Diofant tenglama ko’rinishi quyidagicha: 

 a \cdot x + b \cdot y = c,

  Bu yerda a,b,c-beriladigan butun sonlar, x,y-esa  nomalum butun sonlar.

Quyida biz bu tenglamada bir necha klassik masalalarni ko’ramiz:

§  Ixtiyoriy yechimini topish;

§  Barcha yechimlarini topish;

§  Berilgan kesmadagi yechimlar va ularning sonini topish;

 §  Berilgan kesmadagi yechimlarning eng kichik yig’indisini topish

Mumkin bo’lmagan holati

Mumkin bo’lmagan holatlaridan birini biz ko’rib chiqishdan olib tashlaymiz: bu holat a=b=0 holatidir.

Bunday holat malumki tenglama yo cheksiz ko’p yechimga ega bo’ladi yoki umuman yechimga ega bo’lmaydi(c=0 yoki yo’q holatiga bog’liq).

                                  

                                  Bitta yechimni topish

Ikki nomalumli diofant tenglamaning bitta yechimini kengaytirilgan Evklid algoritmi yordamida topish mumkin.Faraz qilaylik boshida a va b lar musbat.Kengaytirilgan Evklid algoritmida berilgan musbat a va b sondan ularning EKUBi g  va xg , yg koeffisentlari olinadi.

 a \cdot x_g + b \cdot y_g = g.

Agar c koeffisent a va b ning g=gcd(a,b) ga bo’linsa u holda diofant tenglama yechimga ega, aks holda yechimga ega emas.Ushbu tasdiq isboti chiziqli ikki son kombinatsiyasi oldiniga shu sonlarning umumiy bo’luvchisiga bo’linishi shartligidan kelib chiqadi.

                                            Algoritm

Faraz qilaylik agar c koeffisent g=gcd(a,b) ga bo’linsa u holda biz quyidagi tenglamani hosil qila olamiz

 a \cdot x_g \cdot (c/g) + b \cdot y_g \cdot (c/g)[...]

Shunday ekan bizda diofant tenglamaning bitta yechimi mavjud va u quyidagiga teng:

 

                                    

             \cases{

x_0 = x_g \cdot (c / g), \cr

y_0 = y_g [...]

 

Biz olagan javob a va b sonlar faqat musbat holat uchun edi.
Agar ikki sonda biri yoki ikkilasi ham manfiy bo’lsa nima qilamiz
Bunday  holda koeffisentlarni modulini Evklid algoritmi yordamida hisoblab  chiqqan natijani a va b koeffisentlarning holatiga qarab o’zgartiramiz.
Quyida berilga realizatsiyada a=b=0 holat hisobga olinmagan.

                                              Realizatsiya

 static int x0,y0,g;

 static boolean find_any_solution(int a,int b,int c){

    g=gcd((int)Math.abs(a),(int)Math.abs(b));

   if (c % g != 0)

             return false;

          x0=xg* c / g;

          y0= yg*c / g;

            if (a < 0)   x0 *= -1;

            if (b < 0)   y0 *= -1;

            return true;

         }

 

                        Barcha yechimlarini topish

Diofant tenglamaning bitta yechimi(x0,y0) ni bilib turib uning qolgan yechimlarini( ular cheksiz kop) qanday olishni korsatamiz.

Shunday qilib g=gcd(a,b) va x0 va y0 lar ushbu shartni qanoatlantirsin:

 a \cdot x_0 + b \cdot y_0 = c.

.

Bundan korinadiki biz x0 ga b/g ni qoshib shu vaqtning ozida y0 dan a/g ni ayirsak tenglik ozgarmaydi

 a \cdot (x_0 + b/g) + b \cdot (y_0 - a/g) = a \cd[...]

Shubhasiz bu progresni barcha sonlar shaklida qancha hohlasak shuncha takrorlashimiz mumkin.

 \cases{

x = x_0 + k \cdot b/g, \cr

y = y_0 - k [...]

x va y lar diofant tenglamaning yechimlari hisoblanadi.Biz diofant tenglamaning barcha yechimlarini topdik( ko’rinib turilganidek ular cheksiz ko’pdir agar qo’shimcha shart bo’lmasa).

 

Berilgan kesmadagi diofant tenglama yechimlarini va ularning soni topish

[x1;x2] va [y1;y2] kesma berilgan bo’lsin.Bizga malumki agar a yoki b dan biri nolga teng bo’lsa javoblar soni topish qiyin emas.Shuning uchun bu holatlarni oldindan ko’rib qo’yamiz va ishlamoqchi bo’lgan algoritmga ushbu holatlarni o’tkazmaymiz.

Oldiniga x>=x1 shartni qanoatlantiradigan eng kichik xni qiymatini topamiz.Buning uchun tenglamaning ixtiyoriy yechimi topib olamiz.Keyin esa yechim x ni pastgi punktdagi protsedura yordamida oshiramiz/kamaytiramiz toki u eng kichik bo’lib x>=x1 ni qanoatlantirgunicha.

Buni O(1) bilan amalga oshirimiz mumkin.Topilgan sonimiz x1 ga teng yoki undan katta bo’lishi mumkin va uni lx1 deb belgilaymiz.Huddi shunday yo’l bilan maksimal yaqinlashish x=rx1 x<=x2 ham topamiz.

lx1 va rx1 ni topgan keyingi o’zgaruvchi y ni [y1;y2] kesmadan qaraymiz.Yuqoridagi usul yordamida y>=y1 shartni qanoatlantiruvchi eng kichik va y<=y2 bo’ladigan eng katta  y ning qiymatlarini ham topib olamiz.Va ularni lx2 va rx2 orqali belgilaymiz.

Keyin bizda hosil bo’lgan [lx1;rx1] va [lx2;rx2] kesmalarni kesishtirish orqali yangi kesma olamiz va uni [lx;rx] shaklida belgilaymizShunisi aniqki [lx;rx] da yotuvchi x koeffisentlarning ixtiyoriy biri tenglama uchun yechim bo’la oladi.

Bunday holda yechimlar soni [lx;rx] kesma uzunligini |b|ga bo’lib( x  koefffisent qancha o’zgarsa ham +b yoki –b ga o’zgarishi mumkin) unga birni qo’shganimizga teng bo’ladi.

Endi realizatsiyaga o’tsak(u yetarlicha qiyin bo’lib undagi joyiga qo’yiladigan va manfiy bo’ladigan a va b holatlarini etibordan qochirmaslik kerak).

Realizatsiya

static void shift_solution(int a,int b,int cnt){

    x+=cnt*b;

    y-=cnt*a;
}

static int find_all_solution(int a,int b,int c,int x1,int x2,int y1,int y2)  {

         if(!find_any_solution(a,b,c))  

            return 0;

           a /= g;  b /= g;

      int sign_a = a>0 ? +1 : -1;

      int sign_b = b>0 ? +1 : -1;

//x uchun lx1 va rx1 ni aniqlaymiz.

 shift_solution (a, b, (x1 - x) / b);

       if (x < x1)

    shift_solution (a, b, sign_b);

       if (x > x2)

         return 0;

   int lx1 = x;

 shift_solution (a, b, (x2 - x) / b);

       if (x > x2)

  shift_solution (a,b,-sign_b);

                                                 int rx1 = x;

//y uchun lx2 va rx2 ni aniqlaymiz.

  shift_solution(a,b,-(y1-y)/a);

     if (y < y1)

 shift_solution (a,b,-sign_a);

     if (y > y2)

              return 0;

     int lx2 = x;

  shift_solution (a,b,-(y2-y)/a);

      if (y > y2)

   shift_solution (a,b,sign_a);

     int rx2 = x;

// ikki to’plamni kesishtirib javobni olamiz.

   if (lx2 > rx2){

    int t=lx2;

    lx2=rx2;

    rx2=t;

}

   int lx = Math.max(lx1, lx2);

   int rx = Math.min(rx1, rx2);

    if(rx-lx<0) return 0;

    return (rx - lx)/Math.abs(b)+1;

}

Yana bu realizatsiyada barcha yechimlarini chiqarish ham uncha murakkab emas

   Buning uchun x koeffissentni [lx;rx] oraliqda |b| qadam bilan topib va shu qiymat yordamida ax+by=c tenglamadan y ni ham topamiz.

   Va ana shu qiymatlar bizga berilgan kesmadagi barcha yechimlar bo’ladi.

Berilgan kesmadagi eng kichik
           x+y ni topish.

Bu yerda ham x va y qandaydir chegaraga ega bo’lishi kerak aks holda javob har doim minus cheksizlik bo’ladi. Bu javob g’oyasi ham oldingi masalalarga o’xshab ketadi: oldin ixtiyoriy bir diofant tenglama yechimini topamiz

Va uni oldingi punktlardagi kabi boshqa qiymatlarini topishimiz mumkin.

   \cases{

x^\prime = x + k \cdot (b/g), \cr

y^\pr[...]

Ko’rinib turibdiki ularning yig’indisi quyidagicha:

 

x^\prime + y^\prime = x + y + k \cdot (b/g - a/g) [...]

Agar a<b bolsa k ni iloji boricha kichikroq a>b bolsa esa iloji boricha kattaroq qilib olish kerak.

Agar a=b ga bolsa biz javobni yaxshilay olmaymiz chunki hamma javoblar bitta yigindini takrorlaydi.

Mavzuga doir masala:

ACM.SGU.RU da 106

 

Ro`yxatga qaytish        Muallifi: Bahrom Sultonov