Доставка цветов в Севастополе: SevCvety.ru
Главная -> Справочник по алгоритмам

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 [21] 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

на О считается некорректной операцией. Большие погрешности возникают, если д,(*-)0, но является малым числом.

Для повышения точности вычисления определителя и исключения останова ЭВМ в ходе вычислений применяются варианты метода Гаусса с выбором главного элемента по столбцу, строке или по всей матрице. В последнем случае перед преобразованиями в матрице А (3.5) выбирают наибольший по модулю (главный) элемент, допустим а,;. Далее переставляют первую строку матрицы с / й строкой (это и есть выбор главного элемента по строке), а первый столбец переставляют с /-м (выбор главного элемента по столбцу). При каждой такой перестановке знак определителя меняется, поэтому результат нужно умножить на (-1)", где Р - число перестановок.

Программа 3.53.

Пример.

3 4 4 7

= -20.

Отметим, что вычисление этого определителя по программе 3.52 ведет к останову ЭВМ с индикацией ошибки (некорректная математическая операция).

Обратной матрицей называется матрица Л~, произведение которой на заданную матрицу А дает единичную матрицу.

Обращение матрицы А заключается в нахождении обратной матрицы Л". Для обращения матрицы Л используют следующие основные соотношения:

л-л- =

... а\п

... апп

... Х2„

--- . Хпп

Перемножая матрицы А и А получим п систем уравнений с неизвестными:

OllJCll +012X21+ ...-fOin, = 1,

02 ixi I + 02221 + .. + 02„л:„ I = о, a„ix\ 1 + a„2X2i + - -. + a„„x„i =0.

OllX2 + Ol2X22+...+O„X„2 = 0, O2IX12 + O22X22 + .- .+ 02„X„2=l,

0„ 1X12 +0„2X2J + . -. + 0„„X„2 = 0.

o,iXi„+ai2X2„ + ...+oi„x„„ = 0,

O21X„ + 022X2„ + ... -f 02„X„„ = 0,

o„ ix I „+a„2X2„ +,.. + o„„x„„ = 1.

(«)

Решение этих уравнений определяет значения всех элементов матрицы Ллу. Оио выполняется по методам, описанным в § 4.1. Для простых матриц обращение выполняется по программам, реализующим готовые «рецепты» процедуры обращения.

Программа 3.54.

IS PRIHTOEPAUJEHUE МАТРИЦЫ 2*2

2В INPUT-ВВЕДИТЕ Й1ЬЙ12 А/В

25 INPUTВВЕДИТЕ h21..h22 CjD

30 LETE=C*B: LETF=A5 LETE=ri«F-E! LETA=ri.--E

40 1 ЕТГ!=Р>Е: LETC=-C-E: LETB=-B-E

50 PRINT •ОБРАЩЕННАЯ МАТРИЦА

60 PRINT Й.Г В SPRINT С-В г ENB

Пример. 7 8 4 5

л- =

1,66666667 - 2,666666667 -1,333333333 2,333333333

Программа 3.55.

Пример. 4 8 0 8 8 8 2 О 1

л- =

0,083333 - 0,083333 0.66666 0,083333 0,041666 -0,33333 - 0,16666 0,16666 - 0,33333

(указаны 5 значащих цифр результата). Программа 3.56.

Проверить эту программу можно по примеру, приведенному к программе 3.55.

Сложение и вычитание для двух матриц Л и В с одинаковой размерностью тХп производится по формуле

Cij=aij±b,j,

где г = 1, 2, m и / = 1, 2, п. Здесь с,7 - элементы результирующей матрицы С. Программа 3.57. 05 PRINT-СП0Н1ЕНИЕ МАТРИЦ 10 INPUTВВЕДИТЕ МгН МтН 15 BIM Й.;МтН)/Б<М..Н)гС<М/Н) 20 FOR 1=1 ТО MiFOR J=l ТО N 30 PRINT!2,0!ВВЕДИТЕ AIrJ 40 INPUT H<I..J):NEXT J:NEXT I 50 FOR 1=1 TO MS FOR .J=l TO N 60 PR I NTВВЕДИТЕ BI.-J 65 INPUT BajJ> ?0 LETC<bJ)=A<bJ>+Ba,J> 88 NEXT JSHEXT ПЕНИ

Пример. Для

= 2, n = 3

I 2 3

7 8 9

8 10 11

4 5 6

8 7 6

12 12 12

Умножение матриц A с размерностью mXn и В с размерностью пХ/ выполняется по формуле

SMt I (Oftfc.v). 1 = 1

где /=1, 2, ..., / и k=\, 2, .... m. Получаемая матрица С имеет размерность тХ-



10 PRIHT-ОБРАЩЕНИЕ МАТРИЦЫ ЗжЗЛИМ А<3,3>

15 ХНРиТВВЕДИТЕ AlbA12.A13 А< 1/1ЪАСЬ£5Atl..3>

2й ГНРиТВВЕДИТЕ A2bA2£A£3 А;£/1Ь А;2/2)т А<2.-3>

£5 ХНРиТВВЕДИТЕ А31/А3£/А33 АСЗ.-1ЬАСЗ.2:)тАСЗтЗ)

.30 FOR. К,=1 ТО 3

35 LETA=A*;£ 1 УУйС!. 1 >:LETB=-A

40 letc=A<2£)-A*A<b2)!LETri=A«L2..3)-A-*Aa/3>

50 LET А=А < Зг 1 >А а И :>: LET А <. 2f 3 )=-А

60 ЬЕТАС2т1>=А<3/2:5-АжА<12)

?0 LET А 2r 2 ) =А < 3.- 3 ) -А* А < 1 г 3 )

88 LETA;3y 1 )=А; If2)-A< Ь 1)

90 LETA«l3/2>=ACb3)AaT 15

180 LETA<:3j3)=l-Aa/l)!LETA<bl)=c

lie LETA<l7 2)=ri.LETAa/3>=B:NEXT К,

120 PRINTОБРАЩЕННАЯ МАТРИЦА

130 .PRINT А<Ы)тА<12Х.Аа7 3)

140 PRINT AC2rl)..A*L2..2)fAi;2/3)

158 PRINT A<3.. 1)..А<Зг2)/А;ЗгЗ>гЕНГ!

Программа 3-56.

05 PRINTОБРАЩЕНИЕ МАТРИЦ МЕТОДОМ ГАУССА 10 PRINTc ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА 15 1НриТЗАДАйТЕ N=N!liIM A<NtN)j-P<N)N)

20 bim b«lN))C<:n.-n)).g<n),x<n)

25 for 1=1 TO nsfor J=l TO N

30 PRINT12.0!ВВЕДИТЕ ЙIrJ=s INPUT ACbJ) 35 LETPCbJ>=A<bJ)sNEXT JsNEXT I 40 FOR J2=l TO nsfor 1=1 TO N 50 LETB<I)=@sNEXT I 60 LETB<J2)=1

70 FOR J3=l TO NSFOR J4=l TO N

80 LETA<J3/J4>=P<J3fJ4)!NEXT J4SNEXT J3

85 GOSUB 100!FOR 1=1 TO N

90 PRINT!2.0XI.-J2=!F1.9!Xa)

95 NEXT I!NEXT J2SST0P

180 LETNl=N-ls FOR K=l TO N1

110 IF ABS<A<KrK))>8 GOTO 280

120 LETKl=K+lsFOR M=K1 TON

130 IF ABS<A<M.»K,>>>0 goto 150

140 GOTO 165

150 FOR L=l TO N!LETU=A<K/l)sLETA<KrL)=A<MTL)

160 LETA С Mr L > =U!NEXT L s NEXT M

170 LETU=B < К)s LETB < К)=B < M)!LETB < M)=U

200 LET9 < К)=B <К)A< К)s LETK1=K+1

210 FOR I=K1 TO N!LETBa>=B<I>-A<bK)*6«LK)

220 FOR J1=K TO N!LETJ=N-Jl+K!LETC<Kf J)=A«LKrJ).A<K/K>

225 LETA<Ij J)=A<Ir J)-A<bK)»iC<K,r J)

230 NEXT JlsNEXT Is NEXT К

240 LETM=Ns LETX< M)=B<M)A <M >

250 LETM=M-1:L.ETS=0SFOR L=M TO N1

260 LETS=S+c<MrL+l)*X<L+l)!NEXT L

270 letx<:m>=g<:m)-ssif m>i goto 250

280 return:enb . .

Программа 3.58. • •

10 PRINTУМНОЖЕНИЕ МАТРИЦ МжН И N-*l

20 INPUTВВЕДИТЕ MfNrLMrNrL

30 bim A<MrN)/B<NrL)rC«LN/L)

40 FOR 1=1 TO M:F0R J=1 TO N

50 PRINT!2.8!ВВЕДИТЕ AIfJ:INPUT A<IrJ>

68 NEXT JSNEXT I

70 FOR 1=1 TO NSFOR J=l TO L

80 PRINTВВЕДИТЕ ВI, Js INPUT B<I..J>

90 NEXT JSNEXT I

108 FOR K=l TO MsFOR .J=l TO LsLETS=8

110 FOR 1=1 TO NsLETS=S+A<k>I)i«B<b JJsNEXT I

120 LETC<KrJ>=SsNEXT JsNEXT К

138 PRINTРЕЗУЛЬТАТ

140 FOR K,=l TO MSFOR J=l TO L

150 PRINT!2.0!cK:fJ=!F1.9!c<K,, J)

160 NEXT JSNEXT KSEND



Программа 3.58.

Прим ер. Для т-1 2 3

= 4, п = 5, / = 3

j 2 3 4 5

6 7 8 9! 2 3 4 5 6

7 8 9 ! 2

15 30 45 31 62 93 20 40 81 27 54 »t

Умножение Чги г,.....

1 2 3 I 2 3 I 2 3 I 2 3.

матрацы на вектор R== г,,,! выполняется по формуле

где г=1, 2, .... т. В результате получаем вектор £У.={ьь U2, Vm\-

Скалярное произведеЛие векторов А = ={аи 02, oj и В={Ьи bi.....b„] есть число

1 = 1

где /= L 2, п.

Ввиду простоты составления программ для двук последних операций они не приводятся.

§ 3.6. Вычисление и комбинаторика

факториалок

Факториал Цри целом п1

,n! = n-(n-l)-(n-2)-...- 2-1 (3.6)

с особым случаем О! = I у ряда ПЭВМ может вычисляться микропрограммно (найример, с помощью оператора ! у ПЭВМ FX-702P>. Если такой возможности нет, вычисление факториала проводится по формуле (3.6).

Программа 3.S9.

05 РР1ЫТВЫЧИСЛЕНИЕ ФйКТОРИйЛй

10 I№UT ВВЕДИТЕ ЧИСЛО ЧИСЕЛ N=N

20 LET 1=0! LET Р=1

38 LET 1=1+1LET Р=Р*.1

40 IF KN THEN 30

50 PRINT ФЙКТОРИЙЛ N!=P

70 90T0 10! END

Пример 5!= 120, 1О! = 36288О0.

При к -70 значения пГ выходят за rtpe-делы разрядности болвшииства ПЭВМ (п!> Ю).

Для приближенного вычисления -фак-торнала больших чисел п гГрмейяется формула Стирлинга [iO, 36].

Функция пГ! вычисляется по формуле

п!1 =

й(п -2)-...-1 при нечетном п, п(п -2)-...-2 при четном п.

Программа 3.60.

Пример. 7!! = 105, 8!! = 384. Число перестановок. Р„ = п!, а Число размещений из п элемеитов по -т

/4„" = ftV(n -т).. Число сочетаний из й элементов по m

С™ = п!/((п-т)!тГ),-причем п>1 и 1<т<п. Программа 3.61.

Пример. Для m = 5 и /г = IО rfo-лучим

Pi о = 3628800, Л?о=30240 и С?о = 252.

Подобным способом .можно вычислять и другие функции, содержащие члены с факториалами.

Программа 3.60.

85 PRГНТВЫЧИСЛЕНИЕ ФУНКЦИИ N!!

18 INPUTВВЕДИТЕ ЧИСЛО N=N!LETft=N2!LETB=l

15 FOR 1=1 ТО 10

20 IF A-INT<A>=0 THEN 68

30 FOR 1=1 TO N STEP 2

48 ЕЕТВ=Вж1!NEXT I

50 GOTO 80

60 FOR J=2 TO N STEP £ 70 LETB=B*J!NbXT J 80 PRINTЗНАЧЕНИЕ N!!=B 98 GOTO 10!END

Программа 3.61.

18 PRINTРАСЧЕТ Ч1СЛА ПЕРЕСТАНОВОК,- РАЗМЕЩЕНИЙ

28 PRINTИ СОЧЕТЙНИй ИЗ N ЭЛЕМЕНТОВ ПО М

38 INPUTВВЕДИТЕ ЦЕЛЫЕ ЧИСЛЙ Н/ М NrM

40 LETX=N!GOBUB 100!LETP=R

50 LETX=N-M! GOSUB 188! ЕЕТЙ=Р.-Р

60 LETX=M!GOSUB 100sLETC=ftR

76 PRINTЧИСЛО ПЕРЕСТАНОВОК PN=P

80 РРШТЧИСЛО РАЗМЕЩЕНИЙ A M.tN=A

90 PRINTЧИСЛО СОЧЕТАНИЙ С MrN=C!STCP

100 LETR=1EF0R I=X TO 1 STEP -1

110 LETR=R*l!NEXT isRETURNsEND



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 [21] 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78



0.0233
Яндекс.Метрика