Tipi di algoritmi ed esempi

La programmazione sta registrando qualcosa usando la lingua sconosciuta di qualcun altro. Con lo sviluppo di quest'area di conoscenza, gli sviluppatori sono andati oltre e hanno imparato a scrivere "qualcosa", senza nemmeno capire come suona in russo. I principianti imparano a scrivere codice in una volta in C ++ o php usando molte librerie, e non capiscono nemmeno veramente come creano suoni nella loro lingua madre. Algoritmizzazione è impegnata nello spiegare e nel portare a capire questo "qualcosa".

algorithmization

La maggior parte degli esempi di algoritmi per l'informatica, anche nelle università, sono studiati a un livello mediocre. Una pratica comune è la scrittura infinita di codice sempre più complesso. I tentativi da parte di programmatori inesperti di iniziare subito a scrivere programmi nel linguaggio di programmazione possono essere paragonati al lavoro di un giornalista che, a mala pena padroneggiato le basi di una lingua straniera, scrive un articolo per una rivista. Puoi evitare questo problema se inizi a registrare il tuo lavoro prima nella tua lingua, modificalo, controlla gli errori e alla fine traduci nella lingua richiesta.

Il vantaggio di questo approccio è principalmente che lo sviluppatore sarà impegnato nella traduzione solo il 25% delle volte, mentre sta scrivendo un programma in una nuova lingua, che spenderà al 100% per lavorare con una lingua sconosciuta. Allo stesso tempo sarà in condizioni ristrette e non sarà in grado di condurre un buon controllo per errori e perfezionamento del progetto.

L'algoritmo aiuta l'implementazione del progetto su un computer per descrivere il processo di soluzione in un linguaggio nativo e comprensibile sotto forma di un diagramma di algoritmi interconnessi, per analizzare le idee e ottenere il codice più pregiato e di alta qualità che sarà più resistente agli errori e funzionerà in modo più efficiente.

Concetto di algoritmo

Il computer non sa come risolvere i problemi, ma può eseguire solo azioni semplici nell'ordine specificato. "Come è il calcolatore?" - chiedi. È anche il frutto del lavoro dei programmatori che hanno creato un programma che utilizza determinati algoritmi per ottenere i risultati necessari. Considera una situazione astratta. Cosa si dovrebbe fare se vi viene chiesto di trovare le radici del trinomio quadrato di una persona che non ha familiarità con i metodi di risoluzione delle equazioni?

Ovviamente, ha bisogno di essere addestrato per risolvere. equazioni quadratiche. Questo succede come segue:

1. Scegli una soluzione.
2. Esamina tutti i dettagli del metodo selezionato.
3. Spiega i primi due punti del futuro artista in una lingua che lui comprende.

Quindi sarà possibile affidare all'appaltatore i compiti per risolvere un'equazione quadratica. E se i primi due passaggi sono semplici e chiari - tutte le soluzioni sono descritte nella letteratura pertinente, allora il terzo passo è difficile.

Come puoi assicurarti che le idee utilizzate per risolvere il problema saranno percepite dal performer mentre lo comprendi? Qui ci avviciniamo al concetto dell'algoritmo. La pratica dimostra che, per consentire a qualcuno di spiegare correttamente qualcosa, devono essere seguiti i seguenti passi:

• determinare i dati di origine (variabile e coefficienti dell'equazione quadratica);
• dividere il processo decisionale in componenti univocamente noti per l'esecutore (formule discriminanti e ricerca di radici);
• specificare l'ordine dei passaggi (prima calcolare la discriminante, quindi le radici);
• stabilire la condizione in base alla quale la soluzione è considerata completa (controllare le radici trovate, sostituendole nell'equazione per il posto delle variabili);
• indica esattamente come dovrebbe essere il risultato della soluzione (le radici appartengono all'insieme dei numeri reali).

L'insieme descritto di passaggi in senso generale è un algoritmo. Pertanto, l'algoritmo può essere inteso come un metodo per risolvere il problema, scritto con l'aiuto di alcune regole, che consente di fornire una comprensione inequivocabile delle azioni eseguite e del loro ordine. Di seguito verranno discussi in modo più dettagliato gli algoritmi e gli esempi di problemi.

Le principali proprietà dell'algoritmo

Discrete. Il processo di risoluzione di un problema è sempre strettamente separato dalle altre azioni, chiamate fasi, con uno specifico ordine di esecuzione.

Certezza. Ogni passaggio dovrebbe essere chiaro e non ambiguo, sia nel significato che nella chiave dell'azione da intraprendere.

Efficacia. L'algoritmo dovrebbe dare il risultato. In questo caso, il numero di passaggi può essere di migliaia o milioni, ma devono sempre portare a un risultato.

Mass. Qualsiasi algoritmo sviluppato per risolvere un problema dovrebbe essere applicabile a tutti i problemi di questo tipo per tutti i dati di input validi.

Funzionalità del computer

Per creare correttamente algoritmi per computer, è importante capire le loro capacità. Considerare prima le quantità con cui funziona il computer. In generale, possono essere divisi in numeri e testo, costanti e variabili.

I numeri costanti sono tutti i numeri: 3.15, 100, 10 ⁵ , la loro particolarità è l'invarianza in tutto il programma. Le variabili cambiano il loro valore nel corso dell'esecuzione del codice e sono designate, di regola, dalle lettere: x, y, max, min, ecc.

Le variabili di testo, come quelle numeriche, sono costanti o variabili. Nel primo caso, questo è solo il testo: "buono", "aeb", ecc. Nel secondo, il simbolo è lo stesso simbolo delle variabili numeriche: nome, città, ecc. La differenza tra loro si trova principalmente nella memoria allocata del computer sotto la memorizzazione di una tale variabile.

Operazioni che un computer è in grado di eseguire:

1. Leggi i dati dai dispositivi di input (tastiera, mouse, file).
2. Calcolo dei valori usando funzioni matematiche: addizione, sottrazione, sin, cos, ln, ecc. - ogni linguaggio di programmazione ha il proprio insieme di funzioni integrate.
3. Uscita dati (su schermo, su carta, nell'interfaccia di rete).
4. La transizione tra le fasi del programma.
5. Confronto di due quantità (più, meno, uguale).

Queste sono le operazioni di base che possono essere eseguite dalla maggior parte dei linguaggi di programmazione.

Modi per descrivere gli algoritmi

Verbale. Questo è il modo più semplice. Un esempio è la ricetta. È consentito l'uso di semplici formule matematiche.

Graphic. Descrizione utilizzando schemi. Questo è un modo speciale per scrivere algoritmi usando una sorta di linguaggio algoritmico generalmente accettato - figure e blocchi che hanno un significato specifico: un rettangolo è una semplice azione, un parallelogramma obliquo è input / output, un rombo è una condizione, ecc.

L'uso del linguaggio algoritmico. Simile al grafico, questo è anche un modo speciale per scrivere un algoritmo. Ci sono molti linguaggi algoritmici. Le loro regole non sono rigide, altrimenti sarebbe un linguaggio di programmazione. Si consideri un esempio di un algoritmo del libro paga, in base alla durata del servizio, registrato utilizzando un linguaggio algoritmico.

 алг заработная плата (int ST, real ZP)арг STрез ZPначалоесли ST < 5 то zp = 150иначеесли ST <= 15 то ZP = 180иначе ZP = 180 + (ST - 15)*10конец 

Linguaggio algoritmico può essere definito una forma di scrittura più rigorosa di quella verbale. Vengono utilizzate un insieme limitato di parole e le loro costruzioni, oltre all'indentazione. Lo svantaggio della forma verbale e del linguaggio algoritmico è il peggioramento della visibilità dell'algoritmo con l'aumento della sua dimensione. Pertanto, questi metodi possono essere utilizzati solo per trasmettere il significato di piccoli algoritmi.

Tipi di algoritmi

Esiste un'enorme varietà di algoritmi progettati per risolvere vari problemi. Ad esempio, qualsiasi libro di testo di matematica superiore contiene centinaia di algoritmi: soluzione di sistema equazioni lineari trovando gli estremi della funzione, calcolando l'integrale, ecc. Tuttavia, dopo un esame dettagliato della loro struttura, risulta che tutti gli algoritmi possono essere suddivisi in diversi tipi. Considera questi tipi di algoritmi con esempi.

• lineare (calcolo del risultato di addizione o moltiplicazione, lo scambio di valori di più variabili);
• ramificazione (determinando il più grande di più numeri);
• ciclico (ordinamento array, calcolo fattoriale).

Questi sono tipi base. Vale anche la pena notare che in un certo numero di letteratura è anche evidenziato un quarto tipo - ricorsivo. Ma non ha una designazione speciale nella notazione schematica e viene implementata attraverso quelle di base.

Ulteriori dettagli su ciascun algoritmo di calcolo con esempi saranno descritti di seguito.

Principi di algoritmizzazione

1. Identificare i dati di origine.
2. Scegli una soluzione.
3. Dividere il metodo selezionato in passaggi basati sulle funzionalità del computer (linguaggio di programmazione).
4. Esegui l'algoritmo sotto forma di schema, definendo un chiaro ordine di passaggi.
5. Visualizza i risultati dei calcoli.
6. Segna la transizione al circuito di uscita.

Debug degli algoritmi

Una persona commette degli errori, e questo è un dato di fatto. Il parametro principale di qualsiasi algoritmo dovrebbe essere la correttezza del suo lavoro. Il debug è il processo di identificazione e correzione degli errori di un algoritmo. Per fare ciò, prendi un certo insieme di dati sorgente, chiamato test. Sono, di norma, tutti i tipi di dati sorgente. Ad esempio, se viene immesso un numero, l'algoritmo deve essere controllato per il corretto funzionamento, tenendo conto di: numeri positivi, negativi, interi e reali, valori zero, ecc.

Lo strumento principale per verificare l'accuratezza dell'algoritmo rimane il cervello umano. Naturalmente, è consentito utilizzare altri strumenti informatici per automatizzare la verifica, ma in un modo o nell'altro, una persona è impegnata nella preparazione dei test e nell'analisi dei risultati. In questo caso, sorge la domanda, perché abbiamo bisogno di un algoritmo se una persona esegue tutto da solo? Quindi, il compito principale dell'algoritmo è la soluzione multipla di un certo tipo di problemi.

Algoritmi lineari

Un algoritmo lineare è uno in cui i passi seguono uno dopo l'altro. Qualsiasi algoritmo che non contenga rami e cicli è lineare. Considera un esempio di un algoritmo che risolve il seguente problema: un lupo e una lepre siedono in due gabbie, è necessario scambiarle.

La chiave per risolvere questo problema è la temperatura aggiuntiva della cella, che dovrebbe essere utilizzata per scambiare gli animali.

Algoritmi di ramificazione

Come suggerisce il nome, l'algoritmo ha diversi rami. L'essenza del lavoro è scegliere una delle possibili varianti del processo computazionale, a seconda delle condizioni. Una ramificazione schematica è rappresentata da un blocco a forma di diamante, all'interno del quale è indicata la condizione, e ai lati di esso sono i rami di scelta, a seconda che la condizione sia vera o falsa. L'algoritmo di ramificazione e gli esempi della sua applicazione possono essere trovati ovunque. Nella programmazione, questo è un tipico costrutto if-else, che è in quasi tutte le lingue.

Diamo un esempio di un algoritmo per risolvere il problema di trovare il più grande tra i tre numeri.

Algoritmo ciclico

Un ciclico è un algoritmo in cui si verificano ripetizioni multiple degli stessi passaggi, in cui può cambiare solo il valore di una variabile specifica su cui sono fatti i calcoli. I tipi di algoritmo e di esempio ciclico saranno discussi di seguito, ma per ora elencheremo i passaggi principali per la costruzione di un ciclo.

1. Assegnazione del valore iniziale delle variabili. Senza l'adempimento di questa condizione, il ciclo probabilmente non sarà in grado di funzionare o commetterà errori.
2. L'unità che calcola i risultati. Questo è il corpo principale del ciclo.
3. Controllare le condizioni finali del processo ciclico. Se si dimentica di specificare la condizione in base alla quale completare il ciclo, l'algoritmo verrà eseguito a tempo indeterminato.
4. Cambia le variabili Questo blocco ha effetto dopo aver verificato le condizioni della risoluzione, se era falso. Se dimentichiamo questo blocco, il ciclo eseguirà sempre un'azione e non finirà mai. Pertanto, è importante che le variabili subiscano modifiche a ogni iterazione del ciclo.

Esistono diversi tipi di algoritmi ciclici: con postcondizione, precondizione e parametro.

Costruiamo un algoritmo ciclico usando l'esempio di trovare il fattoriale di N.

Altri tipi di algoritmi

Esistono numerosi algoritmi che differiscono per classificazione o origine.

• Algoritmi meccanici. Ad esempio, il funzionamento di un motore a combustione interna o una catena di montaggio.
• Algoritmi probabilistici. Il loro lavoro si basa sulla teoria della probabilità e sulla statistica matematica.
• Algoritmi euristici. Utilizza considerazioni pratiche nel loro lavoro, senza una rigorosa giustificazione matematica.
• Algoritmi genetici. Applicare idee biologiche nel loro lavoro.

E altri