Algoritmni loyihalash va tahlil qilishga kirish

10. Cheksiz takrorlanadigan jarayonlardan foydalanish
Takroriy tsikllar va yaqinlashish
Takroriy tsikl
Shunday qilib, har qanday tsikl jarayon sifatida to'rtta tarkibiy qism bilan tavsiflanishi mumkin:
· Dastlabki holat;
Loop cheklovi (davom etish yoki tugatish sharti):
Keyingi bosqichga o'ting:
· Takroriy harakat - tsikl tanasi.
Aksariyat tsikllarda tsikl tanasida bajariladigan harakatlar uning yo'nalishi parametrlariga ta'sir qilmaydi: qadamlar soni, qadam xususiyatlari. Bunday "yaxshi" tsikllarda tsikl sarlavhasining parametrlari tsikl tanasida hisoblangan o'zgaruvchilar qiymatlariga bog'liq emas va tsikl doimiy takrorlanish soniga ega, masalan:
uchun (i = 0; i Agar tsiklning ma'lum bir bosqichida dasturning xatti-harakatlari oldingi bosqichlarda tsikl tanasi bajarilishining natijalariga bog'liq bo'lishi mumkin yoki tsiklning takrorlanish soni qadam natijalariga bog'liq bo'lsa, bunday tsikllar va ular tomonidan dasturlashtirilgan jarayonlar takrorlanuvchi deb nomlanadi. Ular hisoblash matematikasida, natijada sonli natijani olish uchun unga ketma-ket yaqinlashishning takrorlanadigan tsikli ishlatilganda eng keng qo'llaniladi.
Agar siz takrorlanadigan tsiklning umumiy sxemasini tasvirlasangiz, unda u avvalgi (x1) va hatto undan oldingi (x2, ...) qadamlarning natijasini saqlaydigan o'zgaruvchilarni, shuningdek x o'zgaruvchisini - joriy qadam natijasini o'z ichiga oladi:
uchun (x1 = ..., x2 = ...; shart (x1, x2); x2 = x1, x1 = x) {... x =… x1… x2…; ...}
Obrazli qilib aytganda, agar x "bugungi" qiymat bo'lsa, u holda x1 kecha, x2 esa kecha oldin bo'ladi. Keyingi bosqichga o'tishda "kecha" "kecha oldin", "bugun" - "kecha" ga aylanadi. Takrorlanuvchi tsiklning o'ziga xos xususiyati shundan iborat
Agar takrorlash tsiklida bitta qadam kafolatlangan bo'lsa, unda do ... while tsiklidan foydalanish mumkin.
x = ...; x1 = ...; // Joriy qadamning boshlang'ich qiymati
qil {
x2 = x1; x1 = x; // Keyingi qadam
x =… x1… x2…; // Joriy qadamning natijasi
} while (shart (x2, x1, x)); // Tugatish sharti
Agar siz avvalgi natijaga bog'liq bo'lgan faqat joriy qadam natijasidan foydalansangiz, unda tsikl diagrammasi soddalashtirilishi mumkin.
uchun (x = ...; shart (x);) {... x =… x…; ...}
Takroriy ketma-ketliklar
Matematikadan takroriy ketma-ketliklar ma'lum bo'lib, unda keyingi element bir nechta oldingi qismlardan hisoblanadi. Masalan, Fibonachchi raqamlari navbatdagi element oldingilarining yig'indisiga teng bo'lgan ketma-ketlikdir:
Fn = Fn-1 + Fn-2, F0 = 1, F1 = 1
Ketma-ketlik elementlarini bevosita hisoblashda joriy, oldingi va "kecha oldin" qiymatlarini saqlash uchun uchta o'zgaruvchiga ehtiyoj bor.
// ------------------------------------------------ ------ 43-01.cpp
// --- Fibonachchi raqamlari
int FIBO (int n) {
int Fn, Fn1 = 1, Fn2 = 1;
uchun (int i = 2; i <= n; i ++) {
Fn = Fn1 + Fn2;
Fn2 = Fn1; // Keyingi bosqichga o'ting:
Fn1 = Fn; // joriy oldingi bo'ladi
}
qaytish Fn;}
Yana bir misol, sin (nx), cos (nx) ko'p burchakli sinuslar yoki kosinuslar, bu bizga garmonik qator yig'indisini hisoblashda kerak bo'ladi ("Laboratoriya ustaxonasi" ga qarang). Har safar bir nechta argumentlar uchun funktsiyalarni hisoblash o'rniga sin (x), cos (x) boshlang'ich qiymatlarini bir marta hisoblash va keyin takrorlanadigan formuladan foydalanish kifoya:
sin (nx) = sin ((n-1) x) cos (x) + cos ((n-1) x) sin (x)
cos (nx) = cos ((n-1) x) cos (x) - gunoh ((n-1) x) sin (x)
Dasturda formulani amalga oshirishda sin va cos qiymatlarini joriy nx argumentidan, oldingi (n-1) x dan va boshlang'ich x dan alohida o'zgaruvchilar bilan belgilash kerak. Tsiklning keyingi bosqichiga o'tishda, amaldagilari oldingilariga ko'chiriladi.
// ------------------------------------------------ ------ 43-02.cpp
// --- sin, cos ko'p burchaklari
void main () {
int FI = 30;
er-xotin pi = 3.1415926;
er-xotin Cn, Cn1, C0, Sn, Sn1, S0; // S0 = sin (x), Sn1 = sin ((n-1) x), Sn = sin (nx)
Cn1 = C0 = cos (FI * pi / 180); // n = 2 sin ((n-1) x) = sin (x) uchun
Sn1 = S0 = sin (FI * pi / 180);
printf ("sin (% d *% d) =% lf cos (% d *% d) =% lf \ n", 1, FI, S0,1, FI, C0);
uchun (int n = 2; n <= 10; n ++) {
Sn = Sn1 * C0 + Cn1 * S0; // takrorlanadigan formulalar
Cn = Cn1 * C0 - Sn1 * S0;
printf ("sin (% d *% d) =% lf cos (% d *% d) =% lf \ n", n, FI, Sn, n, FI, Cn);
Cn1 = Cn; // Keyingi bosqichga o'ting
Sn1 = Sn; // joriy oldingi bo'ladi
}}
Taxminiy hisob-kitoblar
Hozircha takrorlanuvchi ko'chadanlar xuddi shu amallarni takrorlash zaruratini bartaraf etib, bizga "hisoblash tejamkorligi" ni taqdim etdi. Hisoblash matematikasida boshqa g'oya ishlaydi. Ketma-ket yaqinlashish usulida qidiruv maydonidagi keyingi nuqtaning koordinatalari oldingi nuqtalarning koordinatalari orqali hisoblanadi va ketma-ketlikning o'zi ma'lum bir xususiyatga ega bo'lgan bir nuqtaga cheksiz yaqinlashadi (yaqinlashadi). Число шагов цикла определяется точностью приближения к предельной точке, а оно, в свою очередь, оценивается расстоянием между текущей и предыдущей.
Сама идея, на каких принципах организовать движение от точки к точке, к программированию, как таковому, не относится. Она лежит в предметной области, откуда и ведутся все доказательства работоспособности метода. Для практического программирования важно следующее:
· число шагов цикла (скорость сходимости) определяется самим методом (функцией, вычисляющей следующую точку), а также начальной точкой;
· Jarayon, aksincha, ajralib turganda, ya'ni holatlar mumkin, ya'ni. Boshlang'ich nuqtadan "uzoqlashadi", koordinata qiymatlarini cheksizgacha oshiradi (dasturda - to'ldirish).
Funktsiyaning ildizini ketma-ket yaqinlashish usuli bilan topishning eng oddiy usulini ko'rib chiqing.F (x) = 0 funktsiyasining ildizini topish uchun x = f (x) + x ekvivalent tenglama echiladi. Agar siz unda ildizning aniq qiymatini almashtirsangiz, unda o'ng va chap tomonlar bir-biriga to'g'ri keladi. Agar o'ng tomonga x1 ning har qanday "begona" qiymatini qo'ysak, chap tomonda biz x1 dan farq qiladigan qiymatni olamiz, masalan x: x = f (x1) + x1. Agar o'ng tomonda x qiymati oldingi bosqichda takrorlanadigan tsiklning natijasi deb hisoblansa (x1), chap tomonda x qiymati tsiklning joriy qadamining natijasi bo'lsa, unda natijaga ketma-ket yaqinlashish jarayoni takrorlanadi.
x = x0;
qil {
x1 = x;
x = f (x1) + x1;
} while (shart (x, x1));
Bu x qiymatlari ketma-ketligi bo'lishi (sonlar o'qidagi nuqtalar) aniq. Agar bu ketma-ketlik yaqinlashsa, u funktsiya ildiziga yaqinlashadi - bu ham ravshan. Bitta savol ochiq bo'lib qolmoqda, ammo u umuman yaqinlashadimi?

43-1-rasm. Tenglamani taxminiy echimining takroriy tsikli
Grafika illyustratsiyasi, isbotlanmasa ham, qanday ishlashini tushuntiradi. Tenglamaning ildizi F (x) + x funksiya grafigi bilan diagonal (y = x funktsiya) ning kesishmasidir. Keyingi x = F (x1) qiymatini hisoblaganimizda, funktsiya grafigidagi x1 ga mos keladigan nuqtani olamiz. X1 = x ni tayinlashda grafika nuqtasi y o'qidan x o'qiga prognoz qilinadi, diagonal atrofida aks ettiriladi. Keyin grafikadagi funktsiyaning qiymati undan olinadi. Rasmda grafadagi bir nuqtadan keyingi nuqtaga bunday o'tishni osonlashtirish mumkinligini ko'rishimiz mumkin: gorizontal chiziq joriy nuqtadan diagonalgacha, so'ngra funktsiya grafigini kesib o'tguncha vertikal chiziq. Ufq bo'ylab harakatlanishning bunday ketma-ketligi - diagonali va vertikal bilan kesishguncha - grafika bilan kesishish bizni ildizga olib borguncha.
Dasturning yakuniy shakli, shuningdek, jarayonning sifat mohiyatini (yaqinlashishini) tekshirishni o'z ichiga oladi. Gap shundaki, ushbu usul f () funktsiyalarining barcha turlari va x0 boshlang'ich qiymatlari uchun muvaffaqiyatli ishlamaydi. Printsipial jihatdan takroriy jarayon, aksincha, ildiz qiymatidan cheksiz masofaga olib kelishi mumkin. Keyin jarayon bir-biridan ajralib turishi aytiladi. Yaqinlashishni tekshirish uchun oldingi bosqichning x va x1 qiymatlari orasidagi farqni eslab qolishingiz kerak.
// ------------------------------------------------ ------ 43-03.cpp
// ---- Funktsiyaning ketma-ket yaqinlashuv usuli bilan ildizi
// boshlang'ich qiymati, aniqligi va tashqi funktsiyaga ko'rsatgich (9.3 ga qarang)
er-xotin topish (er-xotin x, er-xotin eps, er-xotin (* pf) (er-xotin)) {
ikki baravar x1, dd;
int n = 0; // qadam hisoblagich
dd = 100.; // Oldingi interval
qil {
x1 = x; n ++;
x = (* pf) (x1) + x1;
printf ("n =% d x =% lf y =% lf dx =% lf \ n", n, x1, (* pf) (x1), fabs (x1-x));
if (fabs (x1-x)> dd) return 0.; // Jarayon ajralib chiqadi
dd = fabs (x1-x);
}
while (dd> eps);
return x; } // Exit - root qiymati
void main () {printf ("cos (x) = 0 x =% lf \ n", toping (0,0.01, cos)); }
Quvvat seriyasini hisoblash
Keling, avval oddiy "hisoblashdan tejash" variantini ko'rib chiqamiz. F (x, n) = a0 + a1x + a2x2 + a3x3 + ... + anxn shaklidagi polinomning qiymatini hisoblashda, agar polinomni quyidagi shaklda ifodalasak, darajalarni ko'p marta hisoblashdan qochish mumkin:
f (x, n) = ((… ((anx + an-1) x + an-2) x +…) x + a1) x + a0
Qavslar ichiga olingan yig'ilgan qisman summani s orqali belgilab, s = s * x + ai, i = n… 0 takrorlanadigan formulani olamiz. // ------------------------------------------------ ------ 43-04.cpp
// ----- Quvvatli polinom
qo`sh poli (qo`sh A [], qo`sh x, int n) {
int i; juft s;
uchun (s = A [n], i = n; i> = 0; i--) s = s * x + A [i];
qaytish s; }
void main () {double B [] = {4,0,3,1,8}; printf ("% lf \ n", poly (B, 2., 4));}
Ko'pgina standart matematik funktsiyalar ularni kuchlar qatorida kengaytirish orqali hisoblanadi (Teylor seriyasi []). Funktsiyaning aniq qiymati cheksiz qator f (x) = S0 + S1 + S2 + ... Sn + ... ning yig'indisi sifatida aniqlanadi, uning shartlari odatda elementning joriy tartib raqamidan daraja va faktoriallarni o'z ichiga oladi. Ba'zan u boshqa doimiy ifodalarni ham o'z ichiga olishi mumkin (masalan, 2 * 4 * 6 *… 2n juft sonlarining ko'paytmasi, 2n-1 kabi toq koeffitsient va boshqalar).
Masalan, sin (x) funktsiyasini quyidagi qatorlarda kengaytirish mumkin:
sin (x) = x-x3 / 3! + x5 / 5! -x7 / 7! +… + (- 1) n + 1x2n + 1 / (2n + 1)! +…
N-sonli ifoda Sn = (- 1) n + 1x2n-1 / (2n + 1)!, Qator n = 0, S0 = x bilan boshlanadi.
"Yaxshi" quvvat seriyalarining xususiyatlaridan biri shundaki, har qanday atama ketma-ket "quyruq" ning qolgan cheksiz yig'indisidan oshib ketadi. Shu asosda hisoblashning aniqligini keyingi davr qiymati bilan baholash mumkin.
Darajalar, faktoriallar va boshqa doimiy iboralarni "hisoblash" uchun joriy atamani oldingisi orqali hisoblashga imkon beradigan rekursiv formulalar chiqariladi. Buni analitik usulda Sn ning umumiy ifodasini Sn-1 ga bo'lish orqali amalga oshirish mumkin
K (x, n) = Sn / Sn-1 = ((- 1) n + 1x2n + 1 / (2n + 1)!) / ((- 1) nx2n-1 / (2n-1)!)
K (x, n) = - x2 / (2n (2n + 1))
Bir necha qo'shni atamalarni ketma-ket hisobga olgan holda formulani induktiv ravishda olish mumkin. Har bir juftlik uchun konversiya koeffitsienti ko'rsatilib, keyinchalik umumiy shaklga keltiriladi: