Programi 

Dvodimenzionalni nizi. Oblikovanje matrike in izpis njenih elementov. Dvodimenzionalni Pascal nizi - matrike Primeri reševanja problemov z dvodimenzionalnimi Pascal nizi

Dvodimenzionalna matrika v Pascalu se obravnava kot enodimenzionalna matrika, katere tip elementa je prav tako matrika (matrika matrik). Položaj elementov v dvodimenzionalnih pascalovih nizih opisujeta dva indeksa. Lahko so predstavljeni v obliki pravokotne tabele ali matrice.

Razmislite o dvodimenzionalni Pascalovi matriki z dimenzijo 3*3, kar pomeni, da bo imela tri vrstice in vsaka vrstica bo imela tri elemente:

Vsak element ima svojo številko, tako kot enodimenzionalni nizi, zdaj pa je številka že sestavljena iz dveh števil - številke vrstice, v kateri se element nahaja, in številke stolpca. Tako je številka elementa določena s presečiščem vrstice in stolpca. Na primer, 21 je element, ki se pojavi v drugi vrstici in prvem stolpcu.

Opis dvodimenzionalne matrike Pascal.

Obstaja več načinov za deklaracijo dvodimenzionalne matrike Pascal.

Že vemo, kako opisati enodimenzionalne nize, katerih elementi so lahko katere koli vrste, zato so lahko tudi sami elementi nizi. Razmislite o naslednjem opisu vrst in spremenljivk:

Primer opisa dvodimenzionalne matrike Pascal

Vrsta
Vektor = niz<тип_элементов>;
Matrika= niz vektorjev;
Var m: matrika;

Deklarirali smo dvodimenzionalno Pascalovo polje m, sestavljeno iz 10 vrstic, od katerih ima vsaka 5 stolpcev. V tem primeru lahko do vsake i-te vrstice dostopate z m[i], do vsakega j-tega elementa znotraj i-te vrstice pa z m[i,j].

Definicija tipov za dvodimenzionalna polja Pascal se lahko poda tudi v eni vrstici:

Vrsta
Matrika= niz nizov< тип элементов >;
ali še preprosteje:
vrsta
matrika = niz<тип элементов>;

Dostop do elementov dvodimenzionalne matrike ima obliko: M [i, j]. To pomeni, da želimo dobiti element, ki se nahaja v i -ti vrstici in j -tem stolpcu. Glavna stvar pri tem je, da ne zamenjujemo vrstic s stolpci, sicer lahko spet pridemo do neobstoječega elementa. Na primer, dostop do elementa M ima pravilen zapis, vendar lahko povzroči napako v programu.

Osnovne operacije z dvodimenzionalnimi Pascalovimi nizi

Vse, kar je bilo povedano o osnovnih operacijah z enodimenzionalnimi nizi, velja tudi za matrike. Edino dejanje, ki ga je mogoče izvesti na celotnih matricah istega tipa, je dodelitev. To je, če naš program opisuje dve matriki istega tipa, npr.

vrsta
matrix= niz celih števil;
var
a, b: matrika;

potem lahko med izvajanjem programa dodelite matriko a vrednost matrike b(a:= b). Vsa druga dejanja se izvajajo element za elementom in vse veljavne operacije, ki so definirane za podatkovni tip elementov matrike, je mogoče izvesti na elementih. To pomeni, da če je matrika sestavljena iz celih števil, se lahko na njenih elementih izvedejo operacije, definirane za cela števila, če pa je matrika sestavljena iz znakov, se lahko zanje uporabijo operacije, definirane za delo z znaki.

Vnos dvodimenzionalne matrike Pascal.

Za zaporedni vnos elementov enodimenzionalne matrike smo uporabili zanko for, v kateri smo spremenili vrednost indeksa od 1. do zadnjega. Toda položaj elementa v dvodimenzionalni matriki Pascal določata dva indeksa: številka vrstice in številka stolpca. To pomeni, da bomo morali zaporedno spremeniti številko vrstice od 1. do zadnje in v vsaki vrstici ponoviti elemente stolpca od 1. do zadnjega. To pomeni, da bomo potrebovali dve zanki for, pri čemer bo ena ugnezdena v drugi.

Oglejmo si primer vnosa dvodimenzionalne matrike Pascal s tipkovnice:

Primer programa za vnos dvodimenzionalne matrike Pascal s tipkovnice

vrsta
matrix= niz celih števil;
var
a, : matrika;
i, j: celo število; (matrični indeksi)
začeti
for i:=1 to 5 do (zanka za ponavljanje skozi vse vrstice)
readln(a[i,j]); (vnos elementa s tipkovnico v i-ti vrstici in j-tem stolpcu)

Dvodimenzionalni Pascalov niz se lahko napolni naključno, tj. uporabite naključno (N) funkcijo in vsakemu elementu matrike dodelite tudi vrednost nekega izraza. Metoda polnjenja dvodimenzionalne pascalove matrike je odvisna od naloge, ki jo opravljamo, v vsakem primeru pa je treba definirati vsak element v vsaki vrstici in vsakem stolpcu.

Tiskanje dvodimenzionalne matrike Pascal na zaslon.

Tiskanje elementov dvodimenzionalne matrike Pascal se izvaja tudi zaporedno, potrebno je natisniti elemente vsake vrstice in vsakega stolpca. Hkrati bi želel, da se elementi, ki so v isti vrstici, natisnejo drug poleg drugega, t.j. v vrsto, elementi stolpcev pa so bili nameščeni drug pod drugim. Če želite to narediti, morate izvesti naslednje zaporedje dejanj (razmislite o fragmentu programa za matriko, opisano v prejšnjem primeru):

Primer programa za tiskanje dvodimenzionalne matrike Pascal

for i:=1 to 5 do (zanka za ponavljanje skozi vse vrstice)
začeti
za j:=1 do 10 do (iteracija vseh elementov vrstice po stolpcih)
zapiši(a[i,j]:4); (tiskalni elementi, ki se nahajajo v i-ti vrstici matrice v eni zaslonski vrstici, s 4 položaji, dodeljenimi za prikaz vsakega elementa)
writeln ; (preden spremenite številko vrstice v matriki, morate premakniti kazalec na začetek nove vrstice zaslona)
konec ;

Opomba ( je pomembno!): zelo pogosto v študentskih programih pride do napake, ko poskušajo vnesti s tipkovnice ali prikazati matriko, kot sledi: readln (a), writeln (a), kjer A je matrična spremenljivka. Ob tem jih preseneti sporočilo prevajalnika, da spremenljivke te vrste ni mogoče prebrati ali natisniti. Morda vam bo jasno, zakaj tega ni mogoče storiti, če si predstavljate N vrčkov, ki stojijo v vrsti, v vaših rokah pa je na primer kotliček vode. Ali lahko uporabite ukaz »nalijte vodo«, da napolnite vse vrčke hkrati? Ne glede na to, kako se trudite, boste morali natočiti v vsako skodelico posebej. Polnjenje in prikazovanje elementov matrike je treba izvajati tudi zaporedno in po elementih, ker V pomnilniku računalnika se elementi niza nahajajo v zaporednih celicah.

Predstavitev dvodimenzionalne matrike Pascal v pomnilniku

Elementi abstraktne matrike v pomnilniku stroja so fizično locirani zaporedno, v skladu z opisom. V tem primeru vsak element zavzame število bajtov v pomnilniku, ki ustreza njegovi velikosti. Na primer, če je matrika sestavljena iz elementov tipa celo število, bo vsak element zasedel dva bajta. Celotna matrika bo imela S^2 bajtov, kjer je S število elementov v matriki.

In koliko prostora bo zavzel niz, sestavljen iz nizov, tj. matrica? Očitno: S i^S j, kjer je S i število vrstic, S j pa število elementov v vsaki vrstici. Na primer za niz, kot je

Matrika = niz celih števil;

Potrebovali boste 12 bajtov pomnilnika.

Kako se bodo elementi tega polja nahajali v pomnilniku? Oglejmo si postavitev polja M matričnega tipa v pomnilniku.

Za vsak element M tipa celo število sta dodeljeni dve pomnilniški celici. Postavitev pomnilnika se izvede od spodaj navzgor. Elementi so postavljeni po vrstnem redu sprememb indeksa, ki ustreza vzorcu ugnezdene zanke: najprej je postavljena prva vrstica, nato druga, tretja ... Znotraj vrstice so elementi po vrstnem redu: prvi, drugi itd.

Kot vemo, je dostop do katere koli spremenljivke možen le, če je znan naslov pomnilniške celice, v kateri je spremenljivka shranjena. Ko se program naloži, se spremenljivki dodeli poseben pomnilnik, to pomeni, da se med spremenljivko in naslovom celice vzpostavi medsebojno ujemanje. Če pa spremenljivko deklariramo kot matriko, potem program "pozna" naslov začetka matrike, torej njenega prvega elementa. Kako dostopate do vseh drugih elementov matrike? Pri dejanskem dostopu do pomnilniške celice, v kateri je shranjen element dvodimenzionalne matrike, sistem izračuna njegov naslov po formuli:

Addr + SizeElem * Cols *(I -1)+ SizeElem *(J -1),

kjer je Addr dejanski začetni naslov, na katerem se polje nahaja v pomnilniku; I, J – indeksi elementov v dvodimenzionalnem nizu; SizeElem – velikost elementa matrike (na primer dva bajta za elemente tipa integer); Cols – število elementov v vrstici.

Izraz SizeElem * Cols *(I -1)+ SizeElem *(J -1) se imenuje odmik glede na začetek matrike.

Koliko pomnilnika je dodeljenega za polje?

Ne razmišljajmo toliko o tem, koliko pomnilnika je dodeljenega polju (o tem smo razpravljali v prejšnjem razdelku), ampak kakšna je največja dovoljena velikost polja glede na omejeno količino pomnilnika.

Za delovanje programa je pomnilnik dodeljen v segmentih po 64 KB, vsaj eden od njih pa je definiran kot podatkovni segment. V tem segmentu se nahajajo podatki, ki jih bo program obdelal. Nobena programska spremenljivka se ne more nahajati v več kot enem segmentu. Zato tudi če je v segmentu samo ena spremenljivka, opisana kot matrika, ne bo mogla prejeti več kot 65536 bajtov. Skoraj zagotovo pa bodo v podatkovnem segmentu poleg matrike opisane še nekatere druge spremenljivke, tako da dejansko količino pomnilnika, ki ga je mogoče dodeliti matriki, ugotovimo po formuli: 65536-S, kjer je S količina pomnilnik že dodeljen za druge spremenljivke.

Zakaj moramo to vedeti? Da ne bomo presenečeni, če med prevajanjem prevajalnik prikaže sporočilo o napaki o deklaraciji predolge matrike, ko program naleti na opis (pravilen s sintaksnega vidika):

Vnesite myArray= niz celih števil;

Že veste, da je glede na dvobajtno predstavitev celih števil dejansko mogoče deklarirati matriko s številom elementov, ki je enako 65536/2 –1=32767. In potem le, če ni drugih spremenljivk. Dvodimenzionalni nizi morajo imeti še manjše indeksne meje.

Primeri reševanja problemov z dvodimenzionalnimi Pascalovimi nizi

Naloga: Poiščite produkt neničelnih matričnih elementov.

rešitev:

  • Za rešitev tega problema potrebujemo spremenljivke: matriko, sestavljeno na primer iz celih elementov; P – produkt elementov, ki so različni od 0; I, J – matrični indeksi; N, M – število vrstic in stolpcev v matriki.
  • Vhodni podatki so N, M – njihove vrednosti bomo vnesli s tipkovnice; matriko – matriko bomo vnesli v obliki postopka; z uporabo funkcije random().
  • Izhodni podatek bo vrednost spremenljivke P (zmnožek).
  • Za preverjanje pravilnega izvajanja programa je potrebno prikazati matriko na zaslonu; za to bomo formalizirali postopek za prikaz matrike.
  • Napredek pri reševanju problema:

O izvajanju glavnega programa bomo razpravljali najprej malo kasneje:

  • vnesemo vrednosti N in M;
  • Predstavimo dvodimenzionalno Pascalovo matriko, za to se obrnemo na postopek vvod (a), kjer je a matrika;
  • Natisnimo dobljeno matrico, uporabimo postopek tiskanja (a);
  • Priredimo začetno vrednost spremenljivki P =1;
  • Zaporedoma bomo prešli skozi vse vrstice I od 1. do N., v vsaki vrstici bomo prešli vse stolpce J od 1. do M., za vsak element matrike bomo preverili pogoj: če je a ij ? 0, potem bo produkt P pomnožen z elementom a ij (P = P * a ij);
  • Prikažemo vrednost produkta neničelnih matričnih elementov – P;

Zdaj pa se pogovorimo o postopkih.

Komentiraj (je pomembno!) Parameter postopka je lahko katera koli spremenljivka vnaprej določenega tipa, kar pomeni, da je za posredovanje polja kot parametra v proceduro potrebno vnaprej opisati njegov tip. Na primer:

Vrsta
Matrika=niz celih števil;
postopek primer (a: matrika);
..............................

Vrnimo se zdaj k našim postopkom.

Postopek za vnos matrike se imenuje vvod, parameter postopka je matrika in jo je treba posledično posredovati glavnemu programu, zato je treba parameter posredovati s sklicevanjem. Potem bo glava našega postopka videti takole:

Postopek vvod (var m: matrix);

Za implementacijo ugnezdenih zank v proceduro potrebujemo lokalne spremenljivke števca, na primer k in h. Algoritem za polnjenje matrike je bil že obravnavan, zato ga ne bomo ponavljali.

Postopek za prikaz matrike na zaslonu se imenuje print , parameter postopka je matrika, vendar je v tem primeru vhodni parameter, torej posredovan po vrednosti. Glava tega postopka bo videti takole:

Izpis postopka (m: matrika);

In spet, za implementacijo ugnezdenih zank znotraj procedure potrebujemo števce, naj se imenujejo enako - k in h. Algoritem za prikaz matrice na zaslonu je bil opisan zgoraj;

Primer dvodimenzionalnega matričnega programa Pascal

Izdelava programov;
Vrsta
Matrika=niz celih števil;
var
A: matrika;
N, m, i, j: bajt;
P: celo število;
Postopek vvod (var m: matrix);
Var k, h: bajt;
Začeti
Za i:=1 do n do (spremenljivka n za postopek je globalna in zato "znana")
Za j:=1 do m do (spremenljivka m za postopek je globalna in zato "znana")
M:= naključno(10);
Konec;
Izpis postopka (m: matrika);
Var k, h: bajt;
Začeti
Za i:=1 do n naredi
začeti
Za j:=1 do m do
Zapiši (M:4);
Writeln;
konec ;
Konec ;
Začetek (začetek glavnega programa)
Writeln("Vnesite dimenzijo matrike:");
Readln(N, M);
Vvod(a);
Natisni(a);
P:=1;
Za i:=1 do N naredi
Za j:=1 do M do
Če<>0 potem p:=p*a;
Writeln(p);
Konec.

Dvodimenzionalni niz podatkovna struktura, ki hrani pravokotno matriko oblike:

A 11 a 12 a 13 a 14 a 15 ...a 1m a 21 a 22 a 23 a 24 a 25 ...a 2m a 31 a 32 a 33 a 34 a 35 ...a 3m a 41 a 42 a 43 a 44 a 45 ...a 4m a 51 a 52 a 53 a 54 a 55 ...a 5m... ... ... ... ... ... ... a n1 a n2 a n3 a n4 a n5...a nm

  • V matriki je vsak element določen s številko vrstice in številko stolpca, na presečišču katerih se nahaja
  • V Pascalu se dvodimenzionalni niz obravnava kot niz, katerega elementi so linearni nizi (niz nizov). Naslednja dva opisa dvodimenzionalnih nizov sta enaka var masa:matrika niza realnega; var masa: niz realnih;
  • Imenuje se matrika, v kateri je število vrstic enako številu stolpcev kvadratna matrika.
  • Za dostop do elementa matrike morate uporabiti dva indeksa, ki označujeta številko vrstice in številko stolpca. Na primer MojArr1. V tem primeru je element polja (MyArr1) v četrti vrstici in petem stolpcu.
  • Vse, kar je bilo povedano o osnovnih operacijah z enodimenzionalnimi nizi, velja tudi za matrike. Pri ponavljanju skozi matriko po elementih v zanki spremenljivke celoštevilskega tipa delujejo kot indeksi. Tradicionalno se identifikator “ uporablja za označevanje indeksa vrstice jaz “, in stolpec – “ j “.
  • Obdelava matrike je sestavljena tako, da najprej upoštevamo elemente prve vrstice (stolpca), nato druge itd. do zadnje.
  • Če se številka vrstice elementa ujema s številko stolpca ( i = j), to pomeni, da element leži na glavna diagonala matrice.
  • Če element leži na stranski diagonali, potem so indeksi povezani s številom elementov ( n) z naslednjo enakostjo: i + j = n + 1

Opis dvodimenzionalne matrike

Obstaja več načinov za deklaracijo (opis) dvodimenzionalne matrike v Pascalu.

Predhodni opis vrste polja

vrsta matrike = niz celih števil; (niz celih števil) var mass:matrix;

Definiranje spremenljivke kot matrike brez predhodne deklaracije vrste matrike

var masa: niz celih števil;

Inicializacija dvodimenzionalne matrike

Pri inicializaciji dvodimenzionalnih nizov je vsaka vrstica zaprta z dodatnim parom oklepajev:

Const mass:array = ((2,3,1,0), (1,9,1,3), (3,5,7,0));

Vnos/izhod vrednosti elementov dvodimenzionalne matrike

Zelo pogosto se vrednosti elementov polja vnesejo s tipkovnice. Ta metoda podajanja informacij je preveč delovno intenzivna pri delu z velikimi nizi. Za odpravljanje napak v širokem razredu algoritmov je treba takšen vnos informacij nadomestiti z naključnim oblikovanjem elementov niza. Če želite to narediti, uporabite postopek randomiziraj in funkcijo naključen. Pri delu z dvodimenzionalnimi nizi se uporabljajo ugnezdene zanke (običajno zanka s parametrom za).

Polnjenje matrike z naključnimi števili

konst n = 5; m = 10; var i, j:celo število; matrika: niz celih števil; začetek naključnega izbiranja; for i:= 1 do n do (dostop do matričnih vrstic) for j:= 1 do m do (poelementni dostop do stolpcev) matrix := random(100); (v trenutni element postavimo naključno število iz intervala :4); writeln (nova vrstica po izhodu iz notranje zanke) konec;

Primeri reševanja problemov

Primer 1

Oblikovanje problema. Dani pozitivni celi števili M in N. Sestavite celoštevilsko matriko velikosti M × N, v kateri imajo vsi elementi J-tega stolpca vrednost 5·J (J = 1, …, N).

Const m = 7; n = 10; var i, j:byte; matrika: niz celih števil; začetek za i:= 1 do m naredi za j:= 1 do n naredi matriko := 5 * j; ... (izhod matrike)

Primer 2

Oblikovanje problema. Dana so pozitivna cela števila M, N in množica M števil. Oblikujte matriko M × N, v kateri vsak stolpec vsebuje vsa števila iz prvotnega niza (v enakem vrstnem redu).

Const m = 5; n = 7; vektor: niz celih števil = (3, 5, 2, 7, 4); var i, j:byte; matrika: niz celih števil; začni za j:= 1 do n do (vzemi j-ti stolpec) for i:= 1 do m do (dostop do elementov j-tega stolpca po vrsticah) matrix := vector[i]; (izvedba) ... (Izhod nastale dvodimenzionalne matrike)

Domača naloga

  1. Dani pozitivni celi števili M in N. Sestavite celoštevilsko matriko velikosti M × N, v kateri imajo vsi elementi I. vrstice vrednost 10·I (I = 1, …, M).
  2. Dana so pozitivna cela števila M, N in množica N števil. Sestavite matriko velikosti M × N, v kateri vsaka vrstica vsebuje vsa števila iz prvotnega niza (v enakem vrstnem redu).
  3. Dodatno. Dana so pozitivna cela števila M, N, število D in niz M števil. Oblikujte matriko velikosti M × N, v kateri prvi stolpec sovpada z izvirnim nizom števil, elementi vsakega naslednjega stolpca pa so enaki vsoti ustreznega elementa prejšnjega stolpca in števila D (kot rezultat , bo vsaka vrstica matrike vsebovala elemente aritmetične progresije).
  4. Dodatno. Dana je matrika velikosti M × N. Izpiši njene elemente, ki se nahajajo v vrsticah s sodimi številkami (2, 4, ...). Prikaz elementov po vrsticah, ne uporabljajte pogojnega operatorja.

Zadnja lekcija Pascal je bila napisana 7. marca, ko smo se učili . Danes bomo ugotovili, kaj je to dvodimenzionalno polje v pascalu kako je opisano in kaj je. Več podrobnosti spodaj.

Kaj je torej dvodimenzionalni niz? Za lažje razumevanje si predstavljajmo enodimenzionalni niz kot črto, v kateri si vsi elementi sledijo vodoravno, dvodimenzionalni pa kot kvadrat, v katerem so elementi nameščeni tako vodoravno kot navpično. Dvodimenzionalni niz je sestavljen iz vrstic in stolpcev, imenujemo ga tudi matrika ali matrični niz.

Kako so opisani dvodimenzionalni nizi? Obstaja več načinov za pisanje dvodimenzionalnih nizov, obravnaval bom 2 od njih.

1 način za opis matrike: matrika vrste spremenljivk v matriki (celo število/realno/bajt);

2. način za opis matrike: matrika matrike tipa spremenljivk v matriki;

Najprej so opisane vrstice (1..m), nato pa stolpci (1..n).

Druga metoda opisuje, kako sta opisani dve enodimenzionalni matriki, ki skupaj tvorita eno dvodimenzionalno.

Dvodimenzionalno matriko lahko opišete v razdelku Vrsta, za kasnejši dostop do nje večkrat, ali v razdelku Opis spremenljivke Var, rad bi poudaril, da lahko namesto m in n zamenjate številke oz uporabite konstante.

Primer podajanja dvodimenzionalne matrike v razdelku z opisom spremenljivke:

Konst
m = 100;
n = 100;
var
a: Niz celih števil;

V tem primeru smo določili dvodimenzionalni niz a velikosti 100 krat 100, to pomeni, da imamo kvadratno matriko.

Primer podajanja matričnega polja z uporabo razdelka Vrsta:

Konst
m = 100;
n = 100;
Vrsta
Matrika = niz celih števil;
var
a: Matrica;
b:Matrika;

V drugem primeru smo podali dve enaki matrični matriki velikosti 100 krat 100; pri opisu matrike b nam ni bilo treba ponovno opisovati njenih dimenzij in podatkovnega tipa.

Kako dostopati do spremenljivke celice v dvodimenzionalnem nizu?

Za dostop do dvodimenzionalne matrike morate najprej podati številko vrstice in nato številko stolpca, kot sledi:

x je poljubna spremenljivka, a je ime matrike, i je številka vrstice, j je številka stolpca.

Poleg tega sta i in j lahko spremenljivki ali celi števili.

Primer zapisovanja podatkov v matriko:

Za i:= 1 do n do //nastavite številko vrstice v zanki
Za j:=1 do m do //nastavite številko stolpca v zanki
a:=naključno(100); //dodelitev naključne vrednosti celici s številko vrstice i in številko stolpca j

Matriko smo napolnili z naključnimi števili od 1 do 100.

Primer programa z uporabo dvodimenzionalne matrike, v katerem matriko zapolnimo z naključnimi števili in jo prikažemo na zaslonu:

Var //opis spremenljivk in matrike
Matrika: niz celih števil;
i, j: celo število;

Začetek //začetek glavnega programa
writeln("Dvodimenzionalni niz: "); //Dialog z uporabnikom

Za i:= 1 do 10 //izpolnite matriko
za j:= 1 do 10 do
Matrika:=naključno(100);

Za i:= 1 do 10 naredi začetek //Izpis matrike
za j:= 1 do 10 do
napiši (matrika, " ");
writeln
writeln("spletno mesto"); //Če želite, lahko izbrišete
konec; //Konec programa

//readln //uporablja se v Turbo Pascalu