Anagramy przez sortowanie i przez zliczanie znaków. Scenariusz zajęć z informatyki

Scenariusz zajęć z informatyki
Temat: Anagramy przez sortowanie i przez zliczanie znaków
Klasa: III Liceum lub Technikum
Prowadzący: Bartosz Chyś
Data: 11.02.2015r.
Cele szczegółowe:
Uczeń:
- wymienia rodzaje algorytmów sortujących;
- potrafi posegregować liczby stosując wybrany algorytm sortujacy;
- zna pojęcie anagramu;
- podaje przykłady anagramów;
- wskazuje, co oznaczają poszczególne elementy kodu odnoszące się do znajdowania rozwiązania czy dane słowo jest anagramem przy zastosowaniu algorytmów sortujących;
- stosując wybraną metodę sortowania wyszukuje czy dane słowo jest anagramem;
- stosując metodę przez zliczanie wyszukuje czy dane słowo jest anagramem;
- odpowiada na pytania stawiane przez nauczyciela;
- współpracuje z innymi uczniami w celu rozwiązania zadania
Metody:
- podające: opis, wykład informacyjny
- eksponujące: pokaz
- praktyczne: ćwiczenia
Formy: indywidualna, praca w parach, zbiorowa
Środki:
- kolorowe markery;
- tablica multimedialna;
- załączniki- wiedza nauczyciela, wcześniej przygotowane kody w C++
Czas realizacji: 2* 45 minut

Przebieg lekcji
Zajęcia 1
Faza wstępna
1. Czynności organizacyjno-porządkowe
Nauczyciel sprawdza obecność, przedstawia uczniom temat oraz cele zajęć.
Faza właściwa
1. Anagram-definicja
Nauczyciel podaje uczniom definicję anagramu:
Anagramem nazywamy ciągi znaków utworzone w wyniku przestawienia znaków innego łańcucha znaków.
Następnie podaje uczniom przykłady anagramów np.
- algorytm-logarytm;
- tyran-narty;
- alergia-galeria
W dalszej kolejności uczniowie pracując w parach wymyślają anagramy. Nauczyciel spisuje propozycje na tablicy.
2. Powtórzenie wiadomości o algorytmach sortujących
Nauczyciel odwołując się do wiedzy zdobytej na wcześniejszych zajęciach przypomina na czym polega sortowanie bąbelkowe, przez wybór, przez wstawianie, sortowanie szybkie i sortowanie przez scalanie(wiedza dla nauczyciela- załącznik nr 1).
3. Ćwiczenia praktyczne-znajdowanie anagramów przez sortowanie
Nauczyciel prezentuje uczniom kod napisany w języku C++ służący do posortowania znaków w słowach i sprawdzenia czy słowa są anagramem(załącznik 2 do scenariusza). Omawia każdy element kodu. Następnie prosi uczniów o uruchomienie C++ i przepisanie kodu, a następnie sprawdzenie przy użyciu gotowego programu czy dane słowo jest anagramem. Uczniowie sprawdzają słowa wcześniej wypracowane w parach.
4. Znajdowanie anagramów przez zliczanie znaków
Nauczyciel objaśnia uczniom kod służący do znajdowania anagramów przez zliczanie znaków(załącznik 3 do scenariusza). Następnie prosi o uruchomienie programu C++. Uczniowie zgodnie z poleceniem nauczyciela przepisują kody i sprawdzają metodą przez zliczanie znaków, czy słowa które wymyślili są anagramami.
Część końcowa
1. Podsumowanie zajęć
Nauczyciel podsumowuje wiedzę zdobytą przez uczniów podczas zajęć
Uwagi: Scenariusz realizowany w ciągu 2 godzin lekcyjnych. Na jednej godzinie nauczyciel wprowadza metodę anagramów przez sortowanie, a na drugiej metodę przez zliczanie.
Bibliografia:
1) strona internetowa: http://www.algorytm.org
2) strona internetowa http://edu.i-lo.tarnow.pl
3) strona internetowa: http://www.coderscity.pl
4) strona internetowa:Informatyka europejczyka. Podręcznik dla szkół ponadgimnazjalnych- zakres rozszerzony, wyd. PWN;
Załącznik nr 1
do scenariusza

Algorytmy sortujące- wiedza dla nauczyciela
A. Sortowanie bąbelkowe- zasada jego działania opiera się na cyklicznym porównywaniu par sąsiadujących elementów i zamianie ich kolejności w przypadku niespełnienia kryterium porządkowego zbioru. Operację tę wykonujemy dotąd, aż cały zbiór zostanie posortowany.

B. Sortowanie przez wybór- Załóżmy, iż chcemy posortować zbiór liczbowy rosnąco. Zatem element najmniejszy powinien znaleźć się na pierwszej pozycji. Szukamy w zbiorze elementu najmniejszego i wymieniamy go z elementem na pierwszej pozycji. W ten sposób element najmniejszy znajdzie się na swojej docelowej pozycji. W identyczny sposób postępujemy z resztą elementów należących do zbioru. Znów wyszukujemy element najmniejszy i zamieniamy go z elementem na drugiej pozycji. Otrzymamy dwa posortowane elementy. Procedurę kontynuujemy dla pozostałych elementów dotąd, aż wszystkie będą posortowane.
C. Sortowanie przez wstawianie- Najpierw bierzemy pierwszą kartę. Następnie pobieramy kolejne, aż do wyczerpania talii. Każdą pobraną kartę porównujemy z kartami, które już trzymamy w ręce i szukamy dla niej miejsca przed pierwszą kartą starszą (młodszą w przypadku porządku malejącego). Gdy znajdziemy takie miejsce, rozsuwamy karty i nową wstawiamy na przygotowane w ten sposób miejsce (stąd pochodzi nazwa algorytmu - sortowanie przez wstawianie, ang. Insertion Sort). Jeśli nasza karta jest najstarsza (najmłodsza), to umieszczamy ją na samym końcu.
D. Sortowanie szybkie- Zasada jego działania opiera się o metodę dziel i zwyciężaj. Zbiór danych zostaje podzielony na dwa podzbiory i każdy z nich jest sortowany niezależnie od drugiego. Dla zadanej tablicy a[l..p] wybieramy element v=a[l] i przeszukujemy resztę tablicy (tzn. a[l+1..p]) tak długo, aż nie znajdziemy elementu większego niż a[l]. Następnie przeszukujemy tą tablicę od strony prawej póki nie znajdziemy elementu nie większego niż a[l]. Gdy to osiągniemy, zamieniamy miejscami te dwa elementy i zaczynamy cały proces od początku.
E. Sortowanie przez scalanie- Ideą działania algorytmu jest dzielenie zbioru danych na mniejsze zbiory, aż do uzyskania n zbiorów jednoelementowych, które same z siebie są posortowane :), następnie zbiory te są łączone w coraz większe zbiory posortowane, aż do uzyskania jednego, posortowanego zbioru n-elementowego.

Załącznik nr 2
do scenariusza
Znajdowanie anagramu przez sortowanie

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 #include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

bool anagram(string wyraz1, string wyraz2)
{
if (wyraz1.length()!=wyraz2.length())
return false; // dlugosc sie nie zgadza

// sortujemy babelkowo obydwa stringi
for (int i = 0; i<wyraz1.length()-1; i++)
{
for (int j = 0; j<wyraz2.length()-1; j++)
{
if (wyraz1[j]>wyraz1[j+1])
swap(wyraz1[j], wyraz1[j+1]);

if (wyraz2[j]>wyraz2[j+1])
swap(wyraz2[j], wyraz2[j+1]);
}
}

return wyraz1==wyraz2; //zwracamy true lub false
}

int main()
{
string wyraz1, wyraz2;

cout << "Podaj wyraz pierwszy" << endl;
cin >> wyraz1;

cout << "Podaj wyraz drugi" << endl;
cin >> wyraz2;

cout << anagram(wyraz1, wyraz2) << endl;

system("PAUSE");
return 0;
}

Załącznik nr 3
do scenariusza

Znajdowanie anagramu przez zliczanie znaków
#include <stdio.h>
#include <string.h>

void zmien_i_sortuj(char slowo[])
{
char z;
int p,i,s=strlen(slowo);
for (i=0;i<s;i++)
slowo[i]=tolower(slowo[i]);
do
{
p=0;
for (i=1;i<s;i++)
if (slowo[i-1]>slowo[i])
{
z=slowo[i-1];
slowo[i-1]=slowo[i];
slowo[i]=z;
p=1;
}
}
while (p==1);
}

int main()
{
char jeden[1010],drugi[1010];
while (scanf("%s%s",jeden,drugi)!=EOF)
{
zmien_i_sortuj(jeden);
zmien_i_sortuj(drugi);
if (strcmp(jeden,drugi)==0)
puts("TAK");
else
puts("NIE");
}
return 0;
}