środa 19 stycznia 2022 imieniny Henryka i Mariusza 1736 - Urodził się James Watt, inżynier i wynalazca brytyjski
Do końca roku pozostało: 0 dni
Informatyka
Interaktywna mapa szkół
Język polski Historia WOS Sztuka (plastyka i muzyka) Języki obce Religia i etyka
Matematyka Fizyka i astronomia Chemia Biologia Przyroda Geografia Technika Informatyka
Przedmioty zawodowe WF Ścieżki edukacyjne Wychowanie przedszkolne Nauczanie zintegrowane Więcej
Algorytmy i programowanie - zestaw zadań

Palindromy

Palindromem (z greckiego) nazywamy wyraz, który tak samo brzmi, gdy jest czytany wspak.
Palindromami są na przykład takie wyrazy, jak kajak, zaraz, oko, zakaz, mam itp.


Użytkownik wprowadza ciąg znaków s. Podaj algorytm sprawdzania, czy s jest palindromem. (Np.: po wprowadzeniu ciągu znaków kajak w programie powinien pojawić się komunikat „tak”, natomiast po wprowadzeniu ciągu znaków canoe powinien pojawić się komunikat „nie”).

Specyfikacja algorytmu:
 Dane wejściowe:
 ciąg znaków s
 Dane wyjściowe:
 komunikat „tak” lub „nie” w zależności od tego,
 czy s jest palindromem

a)    Przedstaw ten algorytm w formie opisu kolejnych kroków.

b)    Zaprezentuj ten algorytm w formie schematu blokowego.

c)    Napisz program realizujący ten algorytm w wybranym przez siebie języku programowania
       (Pascal, C, lub C++). Oto przykład działania takiego programu:

          Podaj ciąg znak
ów: kajak
          Tak

          Podaj ciąg znaków: canoe
          Nie

d)    Zaimplementuj ten algorytm w formie programu w języku Visual Basic lub skryptu w języku
       JavaScript. Oto przykładowa aplikacja:

     

Podaj wyraz:


Przykładowe rozwiązanie

Poniższe rozwiązanie opiera się użyciu dwóch pomocniczych zmiennych (oznaczmy je przez i oraz j), które oznaczają pozycje znaków w ciągu. Na początku ustawiamy i na początku wyrazu, zaś j na jego końcu. Porównujemy znaki znajdujące się na tych miejscach i jeśli się zgadzają, wtedy i powiększamy o 1, zaś j zmniejszamy o 1, sprawdzamy znaki itd. Procedurę sprawdzania kontynuujemy, jeśli i jest mniejsze od j – nastąpi taki moment, gdy i zrówna się z j lub go przekroczy (zależy to od parzystości liczby znaków w ciągu). Jeśli w jakimkolwiek momencie napotkamy na rozbieżność, czyli różne znaki na miejscach i oraz j, wtedy przerywamy sprawdzanie – sprawdzany ciąg nie jest palindromem. Jeśli natomiast sprawdzanie dobiegło spokojnie do końca, wówczas ciąg jest palindromem.

Ponadto będzie nam potrzebna funkcja zwracająca długość ciągu znaków – przyjmiemy, iż nazywa się ona po prostu długość. Przez s[i] oznaczać będziemy i-ty znak ciągu i założymy, że znaki ciągu s numerowane są od 1 do długość(s).

Specyfikację algorytmu uzupełniamy o poniższy zapis: 

 Zmienne pomocnicze:
 liczby naturalne i, j
 Funkcja pomocnicza:
 długość – jej argumentem jest ciąg znaków, zwraca długość (ilość znaków) tego ciągu
 Notacja:
 s[i] – i-ty znak ciągu sznaki w ciągu numerowane są od 1

Opis kolejnych kroków – pkt a)

Krok 1:   Wczytaj ciąg znaków s.
Krok 2:   Zmiennej i przypisz wartość 1, zaś zmiennej j
 przypisz wartość długość(s).
Krok 3:   Jeśli i jest większe lub równe j, wtedy wypisz komunikat „tak”
 i zakończ działanie algorytmu.
Krok 4:   Jeśli s[i] jest różne od s[j], wtedy wypisz komunikat „nie”
 i zakończ działanie algorytmu.
Krok 5:   Powiększ o 1 zmienną i oraz pomniejsz o 1 zmienną j.
Krok 6:   Przejdź do kroku 3.

 

Schemat blokowy – pkt b)

 

Program w języku Pascal – pkt c)

program Palindrom;

{ Sprawdzanie, czy wprowadzony ciąg znaków jest palindromem }

var
  s: string;
 
i, j: integer;
begin
write('Podaj ciąg znaków: ');
readln(s);
i := 1;         { numer pierwszego znaku }
j := length(s); { numer ostatniego znaku }
while i<j do
 
begin 
  if s[i]<>s[j] then
   
begin
    { znaki różnią się}
   
writeln('Nie');
    halt
    end;
 
{ sprawdzamy dalej }
  i := i+1;
 
j := j-1
  end;
{ sprawdzenie dobiegło pomyślnie do końca }
writeln('Tak')
end.


Program w języku C++ – pkt d)

 

// Sprawdzanie, czy wprowadzony ciąg znaków jest palindromem 

#include <iostream>
#include <string>

// największa długość ciągu znaków
#define MAX 100

main()
{
  char s[MAX+1];    // dodajemy jedno miejsce
                    // na znak zakończenia
  cout << "Podaj ciąg znaków: ";
 
cin >> s;
  int i, j;
 
i = 0;            // numer pierwszego znaku
  j = strlen(s)-1;  // numer ostatniego znaku
 
while(i<j)
  {
    if(s[i]!=s[j])
   
{ // znaki różnią się
      cout << "Nie\n";
      exit(0);
    }
    // sprawdzamy dalej
    i++; j--;
  }
  // sprawdzenie dobiegło pomyślnie do końca
  cout << "Tak\n";

} 
Uwaga: Wartości początkowe zmiennych i oraz j są nieco modyfikowane ze względu na inny sposób numeracji elementów tablicy w języku C++.
 

Program w języku Visual Basic – pkt e)

Pole tekstowe, na którym użytkownik wpisuje ciąg znaków, jest oznaczone jako Text1. Przycisk uruchamiający procedurę sprawdzajacą jest oznaczony jako Command1. Komunikat jest wyświetlany przy użyciu procedury MsgBox.
 

 

 

Oto procedura stowarzyszona z przyciskiem Command1:

Private Sub Command1_Click()
 
Dim s, i, j
  ' odczytanie wprowadzonych danych
  s = Text1.Text
  ' numer pierwszego znaku
  i = 1
  ' numer ostatniego znaku
 
j = Len(s)
  Do While i < j
    If Mid(s, i, 1) <> Mid(s, j, 1) Then
   
' znaki różnią się
     
MsgBox ("Nie")
      Exit Sub
   
End If
    ' sprawdzamy dalej
    i = i + 1
    j = j - 1
  Loop
  ' sprawdzenie dobiegło pomyślnie do końca
 
MsgBox ("Tak")
End Sub

Uwaga: Użycie funkcji Mid umożliwia dostęp do poszczególnych fragmentów ciągu znaków – w tym przypadku do pojedynczych znaków.

Program w języku JavaScript – pkt f)

Prezentujemy kompletny kod HTML strony WWW będącej rozwiązaniem zadania: 

<html> 

  <head>
    <script language=javascript>
     
function sprawdz()
      {
        // odczytanie wprowadzonych danych
       
var s = document.form1.wyraz.value;      
       
var i = 0;           // numer pierwszego znaku
        var j = s.length-1;  // numer ostatniego znaku
       
while(i<j)
       
{
          if(s.charAt(i)!=s.charAt(j))
          { // znaki różnią się
           
alert("Nie");
            return;
         
}
          // sprawdzamy dalej
            i++; j--;
        }
        // sprawdzenie dobiegło pomyślnie do końca
       
alert("Tak");
      }
    </script>
  </head>

  <body>
    <h1 align=center>Palindromy</h1>
    <center>  
      <form name=form1>
        Podaj wyraz: <input type=text size=30 name=wyraz>
        <br><br>
        <input type=button
              
value="Sprawdź czy jest palindromem"
               onClick=sprawdz()>
      </form>
   
</center>
  </body>

</html>





Autor: dr Andrzej Dyrek, mgr Agnieszka Tarnówka-Stec
Komentarze + Dodaj komentarz
  • W Pascalu jak tworzy się instrukcje złozoną to poprzedza sie ją słowem begin, Informatyk (odpowiedzi: 0)
  • Nawiasem mówiac schemat blokowy nie do tego problemu totalna porazka.
  • C++, Animatex (odpowiedzi: 0)
  • C++ jest podobne do języka PAWN
  • SIŁA!, SIŁA! (odpowiedzi: 0)
  • Biorę Double-Blast`a i nie wiem co się dzieje...
  • algorytmy, Pan:** (odpowiedzi: 0)
  • nie wiem o co chodzi :PP
  • Poprawa błędu w C++!, Gniewo (odpowiedzi: 0)
  • #include <iostream> using namespace std; int main() Poprawcie ten początek wtedy rusza. A tak na marginesie to nie wiem jak wy te dzieci do nauki ścisłych przedmiotów chcecie jeżeli zamieszczacie listing nie sprawdzony. Pozdraiwiam!
  • Niezgodność ze standardami., Bronek (odpowiedzi: 0)
  • W przykładzie Java Script powinno być tak. <script language="JavaScript> </script>
  • w c++ liczona jest suma, a nie srednia, * znaczy, że muszę to pole podać? (odpowiedzi: 0)
  • w sumie to tyle... zapomnieli podzielić przez n ;)
  • gggg, gggg (odpowiedzi: 0)
  • co za nudy
  • Blad ???, Wojtas (odpowiedzi: 6)
  • Mam pytanie, czemu w kompilatorze Dev-C++ wyskakuje mi blad, podczas kompilacji ??
  • algorytm c+, student politechnika (odpowiedzi: 0)
  • buhahahhaha. Niezly portal i niezle ucza:) W szczegolnosci podobaja mi sie programy w c++. Ciekawe tylko czy ten doktor, ktory sie pod tym podpisuje kiedykolwiek mial indeks wyzszej uczelni w reku bo juz na pewno nie kierunku informatycznego. Krotko mowiac no comment;
  • schemat blokowy jest od innego zadania, aa (odpowiedzi: 0)
  • a
  • bład w schemacie blokowym algorytmu max(a,b,c,d), Agnieszka (odpowiedzi: 0)
  • schemat blokowy punkt b) nie przedstawia rozwiązania zadania.
  • Kto to pisał?, uczen 2 gimnazjum (odpowiedzi: 2)
  • Nie chciałbym być nie uprzejmy, zawsze uczy sie od tyłu? Przecież takie zadanie można rozwiązać dużo szybciej, stosując konstrukcje języka...
 
Nasi partnerzy:
MEN SchoolNet eTwinning Związek Powiatów Polskich PCSS
Cisco OFEK Przyjazna Szkoła Fundacja Junior FIO CEO
Parafiada net PR Orange IMAX Cinema City WSP TWP
IMAGE PPI-ETC ArcaVir Master Solution Device


Projekt Polski Portal Edukacyjny Interkl@sa
powstał i był realizowany w latach 2000-2011 dzięki wsparciu
Polsko-Amerykańskiej Fundacji Wolności.

W ramach naszej witryny stosujemy pliki cookies w celu świadczenia Państwu usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Państwa urządzeniu końcowym. Możecie Państwo dokonać w każdym czasie zmiany ustawień dotyczących cookies. Więcej szczegółów w naszej "Polityce Prywatności".


Pytania i uwagi: portal@interklasa.pl

Regulamin portalu /  Polityka prywatności /  Ochrona własności intelektualnej /  Zasady korzystania / 
Wyłączenie odpowiedzialności /  Biuro prasowe /  Zasady współpracy /  Redakcja /  Kontakt

Przejdź na stronę ucznia Przejdź na stronę nauczyciela Przejdź na stronę rodzica Certyfikat sieciaki.pl Przyjazna strona kidprotect.pl