C8
Projektowanie algorytmów z wykorzystaniem
wektorów i tablic dwuwymiarowych
wiczenie 1.
Skonstruowa schematy blokowe i opracowa algorytmy w postaci listy kroków dla poni szych algorytmów zapisanych w j zyku Java, a nast pnie zaimplementowa te algorytmy w j zyku C++.
Algorytm 8.1.
import javax.swing.JOptionPane;
public class OcenyNaDwoch {
//tablice deklarujemy jako pola klasy
private String[] przedmioty = null;
private double[] oceny = null;
// rednia
private double srednia = 0;
public static void main(String[] args) {
//tworzymy obiekt naszej klasy
OcenyNaDwoch ocenyNaDwoch = new OcenyNaDwoch();
//wywołujemy stosown metod
ocenyNaDwoch.start();
}
public void start() {
this.pobierzDane();
this.obliczSrednia();
this.wypiszWynik();
}
private void pobierzDane() {
// wczytujemy liczb przedmiotów
int ilePrzedmiotow = Integer.parseInt(
JOptionPane.showInputDialog(null,"Ile przedmitow?"));
// tworzymy obiekty tablic o odpowiedniej wielko ci
this.przedmioty = new String[ilePrzedmiotow];
this.oceny = new double[ilePrzedmiotow];
// wypełniamy tablice danymi
for (int i=0; i < ilePrzedmiotow; i++){
this.przedmioty[i] = JOptionPane.showInputDialog(
1
null,"Podaj przedmiot:");
this.oceny[i] =
Double.parseDouble(JOptionPane.showInputDialog(
null,"Podaj ocene dla "+this.przedmioty[i]+":"));
}
}
private void obliczSrednia() {
for (int i=0; i < this.oceny.length; i++){
this.srednia += this.oceny[i];
}
this.srednia /= this.oceny.length;
}
private void wypiszWynik() {
for (int i=0; i < this.przedmioty.length; i++){
System.out.println((i+1)+". "+this.przedmioty[i]+" =
"+this.oceny[i]);
}
System.out.println("Srednia = "+this.srednia);
}
}
Algorytm 8.2.
import javax.swing.JOptionPane;
public class OcenyNaJednej {
//tablice deklarujemy jako pola klasy
private String[][] przedmioty = null;
//srednia
private double srednia = 0;
public static void main(String[] args) {
//tworzymy obiekt naszej klasy
OcenyNaJednej ocenyNaJednej = new OcenyNaJednej();
//wywolujemy stosowna metode
ocenyNaJednej.start();
}
public void start() {
this.pobierzDane();
this.obliczSrednia();
this.wypiszWynik();
}
private void pobierzDane() {
// wczytujemy ile przedmiotow
int ilePrzedmiotow = Integer.parseInt(
JOptionPane.showInputDialog(null,"Ile przedmiotow?"));
// tworzymy obiekty tablic o odpowiedniej wielkosci
this.przedmioty = new String[ilePrzedmiotow][2];
2
// wypelniamy tablice danymi
for (int i=0; i < ilePrzedmiotow; i++){
this.przedmioty[i][0] = JOptionPane.showInputDialog(
null,"Podaj przedmiot:");
this.przedmioty[i][1] = JOptionPane.showInputDialog(
null,"Podaj ocene dla "+this.przedmioty[i][0]+":");
}
}
private void obliczSrednia() {
for (int i=0; i < this.przedmioty.length; i++){
this.srednia +=Double.parseDouble(this.przedmioty[i][1]);
}
this.srednia /= this.przedmioty.length;
}
private void wypiszWynik() {
for (int i=0; i < this.przedmioty.length; i++){
System.out.println((i+1)+". "+this.przedmioty[i][0]+" =
"+ this.przedmioty[i][1]);
}
System.out.println("Srednia = "+this.srednia);
}
}
Algorytm 8.3.
import javax.swing.*;
public class ParaLiczb {
public static void main(String[] args) {
new ParaLiczb();
}
public ParaLiczb(){
int n, i, j;
boolean istnieje;
String odp, wynik;
odp = JOptionPane.showInputDialog("Podaj liczb elementów tablicy n = ");
n = Integer.parseInt(odp);
int[] t = new int[n];//wprowadzanie danych do tablicy
for(i=0; i<t.length; i++){
odp = JOptionPane.showInputDialog("Podaj " + i +
" element");
//typ String jest zamieniany na typ int
t[i] = Integer.parseInt(odp);
}
//wyprowadzenie elementów tablicy
3
wynik = "";
for(i=0; i<t.length; i++)
wynik += t[i] +" " ;
JOptionPane.showMessageDialog(null, wynik,
"Wczytana tablica",
JOptionPane.INFORMATION_MESSAGE);
//sprawdzanie czy istniej para jednakowych liczb
istnieje = false;
for(i=0; i<n-1; i++)
for(j=i+1; j<n; j++)
if (t[i] == t[j])
istnieje = true;
if (istnieje)
JOptionPane.showMessageDialog(null, "Istnieje
para jednakowych liczb", "PARA",
JOptionPane.INFORMATION_MESSAGE);
else
JOptionPane.showMessageDialog(null, "Nie
istnieje para jednakowych liczb", "PARA", JOptionPane.INFORMATION_MESSAGE);
System.exit(0);
}
}
Algorytm 8.4.
import javax.swing.*;
public class Tablice {
public static void czytajTab(int[] t) {
int i;
String odp;
for(i=0; i<t.length; i++){
odp = JOptionPane.showInputDialog("Podaj " + i + "
element");
t[i] = Integer.parseInt(odp);
}
}
public static void drukujTab(int [] t, String tekst){
String wynik;
int i;
wynik = "";
for(i=0; i<t.length; i++)
wynik += t[i] +" ";
JOptionPane.showMessageDialog(null, wynik, tekst,
JOptionPane.INFORMATION_MESSAGE);
}
}
4
Algorytm 8.5.
import javax.swing.*;
public class SumaElementow {
public static void main(String[] args) {
new SumaElementow();
}
public SumaElementow(){
int n, i;
double Suma = 0;
String odp = JOptionPane.showInputDialog("Podaj liczb elementów tablicy");
n = Integer.parseInt(odp);
int[] t = new int[n];
Tablice.czytajTab(t);
Tablice.drukujTab(t, "Wczytana tablica");
for(i=0; i<n; i++)
Suma = Suma + t[i];
System.out.println("Suma elementów tablicy wynosi " + Suma); System.exit(0);
}
}
Algorytm 8.6.
import javax.swing.*;
public class ParzysteNieparzyste {
public static void main(String[] args) {
new ParzysteNieparzyste();
}
public ParzysteNieparzyste(){
int n, i;
String odp = JOptionPane.showInputDialog("Podaj liczb elementów tablicy n = ");
n = Integer.parseInt(odp);
int[] t = new int[n];
Tablice.czytajTab(t);
Tablice.drukujTab(t, "Wczytana tablica");
System.out.print("Liczby parzyste w tablicy: "); 5
for(i=0; i<n; i++){
if((t[i] % 2) == 0)
System.out.print(t[i]);
}
System.out.println("");
System.out.print("Liczby nieparzyste w tablicy: "); for(i=0; i<n; i++){
if((t[i] % 2) != 0)
System.out.print(t[i]);
}
}
}
ZADANIA DO SAMODZIELNEGO WYKONANIA
ZADANIE 1.
Zadanie przeszukiwania jest nast puj ce. Maj c dan tablic elementów nale y znale
elementy ekstremalne, rozpatruj c trzy
przypadki:
• najwi kszy (max),
• najmniejszy (min),
• najwi kszy (max) i najmniejszy (min).
Wykluczamy rozwi zanie problemu, polegaj ce na zastosowaniu algorytmu sortowania, a nast pnie odczytaniu skrajnych wyrazów ci gu posortowanego. Nale y opracowa schematy blokowe i listy kroków do rozwi zania
problemu,
a
nast pnie
zaimplementowa
otrzymane
algorytmy w j zyku C++ i przetestowa ich działanie.
Wskazówka.
Umieszczamy elementy zbioru w tablicy o wymiarach 1 na n.
Zauwa my, e potrzebne b dzie zadeklarowanie trzech zmiennych:
• zmienna i licz ca nawroty w p tli,
• zmienna max zawieraj ca najwi kszy element zbioru,
• zmienna min zawieraj ca najmniejszy element zbioru.
Przyjmujemy za max (min) dowolny element nale cy do tablicy. Nast pnie dla ka dego innego elementu x znajduj cego si w tablicy powtarzamy działanie: je li x > max, to za max przyjmuj x, oraz je li x < min to za min przyjmij x. Zwracamy uwag na to, e przeszukiwanie musi obj wszystkie elementy tablicy, za wyj tkiem elementu przyj tego za max (min). Znamy wobec tego liczb iteracji, co sugeruje wykorzystanie instrukcji for. Przykładowa implementacja w j zyku Java wyszukiwania max mo e by nast puj ca:
Algorytm 8.7.
import javax.swing.*;
public class MaxTab {
public static void main(String[] args) {
new MaxTab();
}
6
public MaxTab(){
int n, i;
String odp = JOptionPane.showInputDialog("Podaj liczb El. tablicy n = ");
n = Integer.parseInt(odp);
int[] t = new int[n];
Tablice.czytajTab(t);
Tablice.drukujTab(t, "Wczytana tablica");
int max = t[0];
for(i=1; i<n; i++){
if(t[i] > max)
max = t[i];
}
System.out.println("Najwi kszym elementem w tablicy jest liczba " + max);
}
}
Algorytm 8.8.
import javax.swing.*;
public class MinMax {
public static void main(String[] args) {
new MinMax();
}
public MinMax(){
int n, i;
String odp = JOptionPane.showInputDialog("Podaj liczb el. tablicy n = ");
n = Integer.parseInt(odp);
int[] t = new int[n];
Tablice.czytajTab(t);
Tablice.drukujTab(t, "Wczytana tablica");
int max = t[0];
int min = t[0];
for(i=1; i<n; i++){
if(t[i] > max)
max = t[i];
if(t[i] < min)
min = t[i];
}
System.out.println("Najmniejszym elementem w tablicy jest liczba " + min);
System.out.println("Najwi kszym elementem w tablicy jest liczba " + max);
}
}
7
ZADANIE 2.
Maj c dan implementacj w j zyku Java algorytmu sortowania b belkowego, nale y opracowa schemat blokowy i list kroków tego algorytmu, zaimplementowa otrzymany algorytm w j zyku C++ i przetestowa jego działanie.
Algorytm 8.9.
import javax.swing.*;
public class BabelSort1 {
public static void main(String[] args) {
new BabelSort1();
}
public BabelSort1(){
int n, i, temp;
boolean zamiana; //dokonano zamiany - true
String odp = JOptionPane.showInputDialog("Podaj liczb el. tablicy n = ");
n = Integer.parseInt(odp);
int[] t = new int[n];
Tablice.czytajTab(t);
Tablice.drukujTab(t, "Wczytana tablica");
zamiana = true; //ustawienie warto ci pocz tkowej zmiennej
//stwierdzaj cej dokonanie zamiany
while(zamiana){
zamiana = false;
for(i=0; i<n-1; i++)
if(t[i] > t[i+1]){
//zamiana el. i zapami tanie faktu zamiany
temp = t[i];
t[i] = t[i+1];
t[i+1] = temp;
zamiana = true;
}
}
Tablice.drukujTab(t, "Tablica po sortowaniu"); System.exit(0);
}
}
8