Care program este liniar în c. Pe scurt despre programarea liniară

Acasă / Routere

Dacă toate instrucțiunile dintr-un program sunt executate secvenţial, una după alta, un astfel de program este apelat liniar. Luați în considerare, ca exemplu, un program care calculează rezultatul folosind o formulă dată.

Sarcina 1.1. Calcul prin formula

Scrieți un program care convertește temperatura în grade Fahrenheit în grade Celsius folosind formula:

unde C este temperatura în Celsius și F este temperatura în Fahrenheit.

Înainte de a scrie orice program, trebuie să definim clar ce trebuie introdus în el și ce ar trebui să obținem ca rezultat.

ÎN în acest caz,:

Datele inițiale sunt una număr real, care este temperatura în Celsius,

Rezultatul este un alt număr real.

Înainte de a scrie programul, să deschidem mediul integrat Visual C++:

Start/Programe/Microsoft Visual Studio/Microsoft Visual C++ 6.00

1) Fișier > Nou...

2) În fereastra care se deschide:

Selectați tipul de aplicație Win32 Console;

Introduceți un nume pentru proiect în caseta de text Nume proiect;

Introduceți (selectați folosind butonul ...) numele directorului în care se află fișierele de proiect în câmpul de text Locație, de exemplu G:/ASOIZ/

Faceți clic stânga pe butonul OK.

3) se deschide caseta de dialog Win32 Console Application - Stepl of 1 și în ea:

Selectați tipul Un proiect gol;

Faceți clic pe butonul Terminare.

4) După ce faceți clic, va apărea fereastra Proiect nou, în care faceți clic pe butonul OK.

1) Dosar > Nou.... Aceasta va deschide caseta de dialog Nou.

2) În fila Fișiere:

Selectați tipul de fișier (în acest caz: C++ Source File);

În caseta de text File Name, introduceți numele fișierului dorit;

Caseta de selectare Adaugă la proiect trebuie să fie activată;

Faceți clic pe OK.

Introducem următorul text de program:

Să ne uităm la fiecare linie a programului separat.

La începutul programului, este scrisă o directivă de preprocesor, conform căreia un fișier antet este conectat la textul sursă al programului . Acesta este un fișier care conține descrieri ale operatorilor I/O cin și cout.

Orice program C++ constă din funcții, dintre care una trebuie să aibă numele main, indicând faptul că acolo începe execuția programului. După paranteze, corpul funcției este scris între paranteze ( ), adică. acele declarații care trebuie executate.

Orice șablon când scrieți un program are forma:

#include<…>

declararea variabilelor;

introducerea datelor inițiale;

calculul rezultatului;

scoateți rezultatul;

Pentru a stoca datele sursă și rezultatele, trebuie să alocați suficient spațiu RAM. Acest lucru se face folosind declarația 2. Programul nostru trebuie să stocheze două valori: temperatura în Celsius și temperatura în Fahrenheit, astfel încât instrucțiunea definește două variabile. Unul, pentru stocarea temperaturilor în Fahrenheit, se numește fahr, celălalt (în Celsius) se numește cels. Programatorul dă nume variabilelor în funcție de scopul lor. Numele poate consta doar din litere latine, cifre și un caracter de subliniere și nu trebuie să înceapă cu un număr.

Când descrieți orice variabilă, trebuie să o indicați tip. Deoarece temperatura poate lua nu numai valori întregi, tipul real este ales pentru variabile plutesc

Tipuri principale:

int (scurt, nesemnat) – numere întregi,

float (dublu, dublu lung) – real

char – caracter

bool – logic

Pentru ca utilizatorul programului să știe în ce moment este necesar să introducă date de la tastatură, se folosește așa-numitul prompt de intrare (operatorul 3). Specificat în operator este afișat pe ecran. cout linia de caractere și cursorul se deplasează pe linia următoare. Pentru a trece la linia următoare, utilizați endl.

În declarația 4, un singur număr este introdus de la tastatură într-o variabilă fahr. În acest scop este folosit un obiect standard cin si operatia de extragere (citire) >>. Dacă trebuie să introduceți mai multe valori, utilizați lanțul de operații >>.

Operatorul 5 evaluează expresia scrisă în dreapta lui operațiuni de atribuire(notat cu semnul =), iar rezultatul este atribuit variabilei cels, adică stocat în memoria alocată acestei variabile. Primul întreg constanta 5 va fi împărțită la sărut constanta 9, atunci rezultatul acestei operații este înmulțit cu rezultatul scăderii numărului 32 din variabila fahr.

Pentru a afișa rezultatul în operatorul 6, se folosește un obiect cout. Este afișat un lanț format din cinci elemente. Aceasta este linia "Fahrenheit:", valoare variabilă fahr, linie ", în grade Celsius:", valoare variabilă celsși operatorul de linie nouă endl.

Ultima declarație (afirmația 7) a acestui program are scopul de a reveni din el și de a transfera valoarea în mediul extern.

Apoi, compilam programul. Pentru a face acest lucru, apăsați butonul de pe bara de instrumente sau combinația de taste Ctrl+F7. Fereastra de ieșire (în partea de jos a ecranului) ar trebui să afișeze mesajul 0 eroare(e), 0 avertisment(e) (0 erori, 0 avertismente). Dacă există erori, verificați cu originalul.

Pentru a porni programul, apăsați butonul de pe bara de instrumente sau combinația de taste Ctrl+F5.

La pornirea programului, în loc de caractere rusești, vedem ???, care este cauzat de diferite standarde de codificare a caracterelor chirilice în sisteme de operare DOMNIȘOARĂ DOS și Windows. Pentru a remedia acest lucru, adăugați funcția CharToOem în program (adăugările sunt evidențiate cu roșu pentru claritate)

#include

char* RUS(const char* text)

CharToOem(text, buf);

float fahr, cels;

cout<

cels=5/9 * (fahr - 32);

cout<

Funcţie Rus() nu poate fi folosit de mai multe ori într-un lanț de operațiuni<< для одного объекта cout, așa că l-am împărțit în două.

După cum puteți vedea, rezultatul rulării programului cu stabilitate este zero! Acest lucru se întâmplă din cauza modului în care este evaluată expresia. Să ne uităm din nou la operatorul 4. Constantele 5 și 9 sunt de tip întreg, deci rezultatul împărțirii lor este tot un întreg. Desigur, rezultatul calculelor ulterioare nu poate fi altceva decât zero. Corectarea acestei erori este simplă - trebuie doar să scrieți cel puțin una dintre constante ca număr real, de exemplu:

cels = 5. / 9 * (fahr - 32);

Lucrare de laborator nr 1

Subiect: „Programarea algoritmilor liniari. Lucrul cu depanatorul"

Scopul lucrării

1.1 Stăpânirea celei mai simple structuri de program în limbaj C.

1.2 Dobândirea abilităților de organizare a intrărilor/ieșirilor în limbajul C.

Suport tehnic

2.1 Computer personal

2.2 Tastatură.

2.3 Afișare

2.4 Dispozitiv de imprimare.

Software

3.1 Sistem de operare Windows

3.2 Sistem de programare Visual C++ versiunea 6.0 sau Borland C++ versiunea 3.1 și versiunile ulterioare.

Enunțarea problemei

Scrierea unui program simplu cu procesare de date.

5.1 Tema și scopul lucrării.

5.2 Enunțarea problemei.

5.3 Textul programelor.

5.4 Rezultatele executării programului.

5.5 Diagrame de algoritm de program.

Informații generale

Program liniar

Sarcina 1.1. Calcul prin formula

Scrieți un program care convertește temperatura în grade Fahrenheit în grade Celsius folosind formula:

unde C este temperatura în Celsius și F este temperatura în Fahrenheit.

Înainte de a scrie orice program, trebuie să definim clar ce trebuie introdus în el și ce ar trebui să obținem ca rezultat.

În acest caz:

Datele inițiale sunt un număr real care reprezintă temperatura în Celsius,

Rezultatul este un alt număr real.

Înainte de a scrie programul, să deschidem mediul integrat Visual C++:

Start/Programe/Microsoft Visual Studio/Microsoft Visual C++ 6.00

1) Fișier > Nou...

2) În fereastra care se deschide:

Selectați tipul de aplicație Win32 Console;

Introduceți un nume pentru proiect în caseta de text Nume proiect;

Introduceți (selectați folosind butonul ...) numele directorului în care se află fișierele de proiect în câmpul de text Locație, de exemplu G:/ASOIZ/

Faceți clic stânga pe butonul OK.

3) se deschide caseta de dialog Win32 Console Application - Stepl of 1 și în ea:

Selectați tipul Un proiect gol;

Faceți clic pe butonul Terminare.

4) După ce faceți clic, va apărea fereastra Proiect nou, în care faceți clic pe butonul OK.

1) Dosar > Nou.... Aceasta va deschide caseta de dialog Nou.

2) În fila Fișiere:

Selectați tipul de fișier (în acest caz: C++ Source File);

În caseta de text File Name, introduceți numele fișierului dorit;

Caseta de selectare Adaugă la proiect trebuie să fie activată;

Faceți clic pe OK.

Introducem următorul text de program:

Să ne uităm la fiecare linie a programului separat.

Orice șablon când scrieți un program are forma:

#include<…>

declararea variabilelor;

introducerea datelor inițiale;

calculul rezultatului;

scoateți rezultatul;

Pentru a stoca datele sursă și rezultatele, trebuie să alocați suficient spațiu în RAM. Acest lucru se face folosind declarația 2. Programul nostru trebuie să stocheze două valori: temperatura în Celsius și temperatura în Fahrenheit, astfel încât instrucțiunea definește două variabile. Unul, pentru stocarea temperaturilor în Fahrenheit, se numește fahr, celălalt (în Celsius) se numește cels. Programatorul dă nume variabilelor în funcție de scopul lor. Numele poate consta numai din litere latine, cifre și un caracter de subliniere și nu trebuie să înceapă cu un număr.

Când descrieți orice variabilă, trebuie să o indicați tip. Deoarece temperatura poate lua nu numai valori întregi, tipul real este ales pentru variabile plutesc

Tipuri principale:

int (scurt, nesemnat) – numere întregi,

float (dublu, dublu lung) – real

char – caracter

bool – logic

Instrucțiunea 4 efectuează introducerea de la tastatură

În acest scop este folosit un obiect standard cin si operatia de extragere (citire) >>. Dacă trebuie să introduceți mai multe valori, utilizați lanțul de operații >>.

Ultima declarație (afirmația 7) a acestui program are scopul de a reveni din el și de a transfera valoarea în mediul extern.

Pentru a porni programul, apăsați butonul de pe bara de instrumente sau combinația de taste Ctrl+F5.

La pornirea programului, în loc de caractere rusești, vedem ???, care este cauzat de diferite standarde de codificare a caracterelor chirilice în sistemele de operare MS DOS și Windows. Pentru a remedia acest lucru, adăugați funcția CharToOem în program (adăugările sunt evidențiate cu roșu pentru claritate)

#include

char* RUS(const char* text)

CharToOem(text, buf);

float fahr, cels;

cout<

cels=5/9 * (fahr - 32);

cout<

Funcţie Rus() nu poate fi folosit de mai multe ori într-un lanț de operațiuni<< для одного объекта cout, așa că l-am împărțit în două.

cels = 5. / 9 * (fahr - 32);

Programele formate din comenzi simple (operatori) se numesc liniare.
Comenzile simple (instrucțiuni simple ale algoritmului) sunt comenzi care nu folosesc condiții în timpul executării lor. Operatorii simpli includ comenzi (operatori) de atribuire, intrare și ieșire și apelarea unui algoritm auxiliar (subrutină).

Operator de atribuire. Setează sau schimbă valoarea curentă a unei variabile. Aceasta modifică conținutul unui element de memorie specific alocat pentru această variabilă. Deoarece scopul oricărui algoritm este de a obține valoarea dorită într-o anumită locație de memorie, aproape orice program conține acest operator. Operatori I/O. Procedurile standard de introducere a datelor sunt utilizate pentru a determina valorile inițiale ale anumitor variabile și constau dintr-un nume de procedură și o listă de intrare care conține numele variabilelor ale căror valori vor fi introduse de la tastatură sau dintr-un fișier, de exemplu. Variabilelor li se vor atribui valori specifice.
Mai des, pentru a determina valorile inițiale, este mai convenabil să utilizați comanda de intrare, mai degrabă decât comanda de atribuire, deoarece dacă trebuie să utilizați programul cu date inițiale diferite, nu trebuie să modificați textul programului.
Dacă înregistrarea algoritmului conține o comandă de intrare, atunci execuția acesteia este întreruptă și controlul este transferat unui program care poate introduce date. După introducerea datelor, controlul este transferat la următoarea comandă a algoritmului.
În Pascal, procedura de introducere a datelor arată astfel:
CITEȘTE (listă de intrare);
READLN (listă de intrare).
Când sunt executate procedurile READ și READLN, programul intră în starea de așteptare a introducerii datelor. Dacă în lista de intrare sunt specificate mai multe variabile, atunci acestea pot fi introduse pe o linie, separate între ele printr-un caracter spațiu, sau în rânduri separate (într-o coloană), completând introducerea fiecărei valori cu tasta Enter.
Procedura nu se va finaliza până când nu au fost introduse valori pentru toate variabilele din listă. Tipul de valori introduse trebuie să se potrivească cu cel al variabilei corespunzătoare.
Instrucțiunea READLN diferă de instrucțiunea READ prin aceea că, după ce a fost introdusă cantitatea necesară de date, cursorul se deplasează pe linia următoare.
Dacă datele sunt introduse de la tastatură, atunci lista de intrare este o listă de variabile, de ex. o succesiune de nume de variabile separate prin virgule. Dacă intrarea este dintr-un fișier, atunci prima variabilă din lista de intrare este variabila fișier, asociată cu numele fișierului real.
Procedurile standard pentru ieșirea rezultatelor calculelor sunt utilizate pentru a afișa valorile acestora pe un ecran, imprimantă sau fișier. În Pascal, procedurile de inferență arată astfel:
SCRIE (listă de ieșiri);
WRITELN (listă de ieșiri).
Lista elementelor de ieșire este mult mai largă decât în procedurile de intrare. Aceasta poate include:
identificatori ai cantităților ale căror valori vor fi transmise dispozitivului sau fișierului corespunzător;
expresii a căror valoare va fi mai întâi calculată și apoi transmisă dispozitivului;
au devenit valori (numerice, simbolice, șir).
Diferența dintre WRITE și WRITELN este că ieșirea instrucțiunii WRITE începe de la locația curentă a cursorului pe ecranul monitorului, iar cursorul rămâne pe aceeași linie după terminarea ieșirii. Instrucțiunea WRITELN tipărește valorile din poziția curentă, iar apoi cursorul se deplasează pe linia următoare. Puteți utiliza instrucțiunea WRITELN fără o listă de ieșire pentru a muta cursorul pe o linie nouă.
Dacă ieșirea este către un ecran de monitor, atunci lista de ieșire este o listă de variabile sau o secvență de nume de variabile, constante sau expresii separate prin virgule. Dacă rezultatul este către un fișier, atunci prima variabilă din lista de ieșire este variabila fișier, asociată cu numele fișierului real.
În comanda de ieșire, după elementul listă de ieșire, puteți specifica formatul de ieșire, separat prin două puncte, adică. lățimea ecranului pe care vor fi amplasate valorile. Când afișați date reale, puteți specifica și numărul de cifre zecimale din partea fracționară pe care doriți să o afișați.
Exemplu: scrieți (A: 10: 3, B: 8).
Operator pentru apelarea unui algoritm auxiliar. Pascal implementează subrutine de procedură și subrutine de funcție. O subrutină este numită după numele său, indicând parametrii actuali. În acest caz, în locul argumentelor reale pot exista valori specifice, nume ale variabilelor reale, expresii și în locul rezultatelor - doar nume ale variabilelor reale. În acest caz, numărul, tipurile și scopul parametrilor formali și actuali din listele corespunzătoare de parametri trebuie să se potrivească.

Mai sus am examinat diverse probleme practice care pot fi reduse la o schemă de programare liniară. În unele dintre aceste probleme, constrângerile liniare au avut forma inegalității, în altele - egalități, în altele - ambele.

Aici vom lua în considerare o problemă de programare liniară cu constrângeri de egalitate - așa-numita problemă de programare liniară de bază (BLP).

În viitor, vom arăta cum puteți trece de la o problemă cu constrângeri de inegalitate la un OPLP și înapoi.

Problema principală a programării liniare este prezentată după cum urmează.

Există o serie de variabile

Este necesar să se găsească astfel de valori nenegative ale acestor variabile care să satisfacă sistemul de ecuații liniare:

și, în plus, ar minimiza funcția liniară

Evident, cazul în care o funcție liniară trebuie transformată nu la minim, ci la maxim, poate fi redus cu ușurință la cea anterioară, dacă schimbăm semnul funcției și luăm în considerare funcția.

Să fim de acord să numim orice set de variabile o soluție admisibilă a OLP

satisfacerea ecuaţiilor (2.1).

Vom numi soluția optimă aceea a soluțiilor admisibile la care funcția liniară (2.2) devine minimă.

Problema de bază de programare liniară nu are neapărat o soluție.

Se poate dovedi că ecuațiile (2.1) se contrazic între ele; se poate dovedi că au o soluție, dar nu în zona valorilor nenegative. Atunci OLP nu are soluții admisibile. În cele din urmă, se poate dovedi că există soluții admisibile ale OLP, dar printre ele nu există una optimă: funcția L din regiunea soluțiilor admisibile este nemărginită de jos.

Ne vom familiariza cu exemple de astfel de caracteristici ale OPLP mai târziu.

Să luăm în considerare, în primul rând, problema existenței unor soluții admisibile la OLP.

Când rezolvăm această problemă, putem exclude din considerare funcția liniară L care trebuie redusă la minimum - prezența soluțiilor fezabile este determinată numai de ecuațiile (2.1).

Deci, să existe un sistem de ecuații (2.1). Există valori nenegative care satisfac acest sistem? Această problemă este luată în considerare într-o ramură specială a matematicii - algebra liniară.

Să prezentăm pe scurt câteva prevederi ale algebrei liniare, fără să ne oprim asupra demonstrațiilor teoremelor corespunzătoare.

Matricea unui sistem de ecuații liniare

este un tabel alcătuit din coeficienţii pt

O matrice extinsă a unui sistem de ecuații liniare este aceeași matrice completată cu o coloană de termeni liberi:

Rangul unei matrice este ordinul cel mai înalt al unui determinant diferit de zero care poate fi obținut prin ștergerea unor rânduri și a unor coloane din matrice.

În algebra liniară se dovedește că pentru ca sistemul de ecuații liniare (2.1) să fie consistent, este necesar și suficient ca rangul matricei sistemului să fie egal cu rangul matricei sale extinse.

Exemplul 1. Având în vedere un sistem de trei ecuații cu patru necunoscute:

Stabiliți dacă acest sistem este colaborativ?

Soluţie. Matricea sistemului:

Matrice extinsă:

Să determinăm rangul primei matrice. Nu poate fi mai mare de 3 (deoarece numărul de rânduri este 3). Să creăm un determinant ștergând o coloană din matrice, de exemplu, ultima. Primim

Calculând acest determinant după regula binecunoscută, obținem:

Acest determinant nu este egal cu zero, ceea ce înseamnă că rangul matricei sistemului este egal cu 3. Evident, rangul matricei extinse este, de asemenea, egal cu 3, deoarece același determinant poate fi compus din elemente. a matricei extinse. Din egalitatea rangurilor matricelor rezultă că sistemul de ecuații este consistent.

Exemplul 2. Investigați compatibilitatea unui sistem de două ecuații cu trei necunoscute:

Soluţie. Matrice de sistem extinsă:

(partea stângă este matricea sistemului).

Să găsim rangul matricei sistemului compunând toți determinanții posibili de ordinul doi:

Deci, toți determinanții posibili de ordinul doi compuși din elemente ale matricei sistemului sunt egali cu zero; Aceasta înseamnă că rangul acestei matrice a sistemului este

Să găsim rangul matricei extinse. Determinant

Prin urmare, rangul matricei extinse nu este egal cu rangul matricei sistemului: Grfg, prin urmare, sistemul de ecuații este inconsecvent.

Exemplul 3. Investigați consistența unui sistem de trei ecuații cu patru necunoscute:

Soluție Matrice de sistem extinsă (împreună cu matricea de sistem):

Să găsim rangul matricei sistemului. Să luăm un determinant de ordinul al treilea compus din elementele sale, de exemplu:

Se știe că, dacă orice rând al unui determinant este o combinație liniară a celorlalte două rânduri ale sale, atunci determinantul este egal cu zero. În cazul nostru, a treia linie este o combinație liniară a primelor două: pentru a o obține, este suficient să adăugați prima linie cu dublul celui de-al doilea Prin urmare.

Este ușor de verificat că orice determinant de ordinul trei compus din elemente ale matricei sistemului are aceeași proprietate. Prin urmare, rangul matricei sistemului este.

Deoarece există un determinant de ordinul doi diferit de zero, de exemplu,

atunci rangul matricei sistemului este egal cu

Folosind același raționament, ne asigurăm că rangul matricei extinse este egal cu doi: Prin urmare, sistemul de ecuații este compatibil

Rețineți că cele trei ecuații din acest exemplu nu sunt independente: a treia poate fi obținută din primele două prin înmulțirea celei de-a doua cu două și adunând-o la prima. Aceasta înseamnă că a treia ecuație este o consecință simplă a primelor două. Există doar două ecuații independente în sistem: acest lucru este reflectat de faptul că rangul matricei sistemului

Deci, dacă sistemul de ecuații-constrângeri al OLP este consistent, atunci matricea sistemului și matricea sa extinsă au același rang.

Acest rang general se numește rangul sistemului; nu reprezintă nimic mai mult decât numărul de ecuații liniar independente dintre constrângerile impuse.

Evident, rangul sistemului nu poate fi mai mare decât numărul de ecuații:

De asemenea, este evident că rangul sistemului nu poate fi mai mare decât numărul total de variabile:

Într-adevăr, rangul unei matrice de sistem este definit ca ordinul cel mai înalt al determinantului compus din elemente de matrice; întrucât numărul liniilor sale este egal cu , atunci ; deoarece numărul coloanelor sale este egal cu , atunci .

Structura unei probleme de programare liniară depinde în mod semnificativ de rangul sistemului de constrângeri (2.1).

Să luăm în considerare mai întâi cazul când , adică când numărul de ecuații liniar independente incluse în sistemul (2.1) este egal cu numărul de variabile n Să renunțăm la ecuațiile „extra” care sunt combinații liniare ale altora. Sistemul de ecuații-constrângeri al OZLP ia forma:

Deoarece determinantul, compus din coeficienți,

nu este egal cu zero. Din algebră se știe că în acest caz sistemul (2.4) are o soluție unică. Pentru a afla cantitatea, este suficient să înlocuiți coloana din determinant cu o coloană de termeni liberi și să împărțiți cu.

Deci, când sistemul de ecuații de constrângere al OLP are o soluție unică:

Dacă în această soluție cel puțin una dintre cantități este negativă, aceasta înseamnă că soluția rezultată este inacceptabilă și, prin urmare, OPLP nu are soluție.

Dacă toate cantitățile sunt nenegative, atunci soluția găsită este admisibilă. De asemenea, este, evident, optim (pentru că nu există altele).

Evident, acest caz banal nu ne poate interesa.

Prin urmare, în viitor vom lua în considerare numai cazul când, adică atunci când numărul de ecuații independente pe care variabilele trebuie să le satisfacă sunt numerele variabilelor în sine. Atunci, dacă sistemul este consistent, are infinit de soluții. În acest caz, putem atribui variabilelor valori arbitrare (așa-numitele variabile libere), iar variabilele rămase vor fi exprimate prin ele (vom numi aceste variabile de bază).

Alegerea editorului