23. ZADATAK - NOTE - REŠENJE
Ovaj zadatak bavi se osnovnim konceptima muzičke teorije, posebno tonovima unutar oktave i njihovim transponovanjem. Transponovanje podrazumeva pomeranje niza tonova za zadat broj pozicija naviše ili naniže, uzimajući u obzir osnovne tonove i međutonove. U nastavku je objašnjeno kako se koristi jednostavan algoritam za prepoznavanje tonova i njihovo transponovanje uz primenu modulo operatora za cikličko pomeranje tonova. Rešenje se postepeno poboljšava korišćenjem efikasnijih struktura podataka i pretrage.
Rešenje sa upotrebom nizova i sa linearnom pretragom niza
U nastavku je prikazano rešenje:
#include <iostream>
using namespace std;
/*
Tonovi se u muzici ređaju po oktavama, koje se sastoje od po 7 osnovnih tonova (bele dirke na klaviru)
i 5 povišenih/sniženih tonova (crne dirke na klaviru). Osnovni tonovi su C, D, E, F, G, A, H, dok se
povišeni/sniženi tonovi nalaze između tonova C i D (to je ton C# tj. D♭), zatim između D i E (to je ton
D# tj. E♭), između F i G (to je ton F# tj. G♭), između G i A (to je ton G# tj. A♭) i između A i H (to je ton A#
tj. H♭, koji se nekada obeležava i sa B). Dogovorimo se da ćemo sve međutonove obeležavati kao povišene
(korišđenjem oznake #). Tada se svi tonovi ređaju na sledeći način:
C, C#, D, D#, E, F, F#, G, G#, A, A#, H, C, C#, D, D#, E, F, ....
Transponovanje neke melodije znači njeno pomeranje za određeni broj tonova naviše ili naniže. Napiši
program koji transponuje unetu melodiju tj. uneti niz tonova.
Opis ulaza
Sa standardnog ulaza se unosi niska od najviše 1000 karaktera koja sadrži niz tonova koje treba transponovati, a zatim i broj između -11 i 11 koji označava za koliko tonova je potrebno transponovati taj niz
tonova.
Opis izlaza
Na standardni izlaz transponovani niz tonova.
Primer 1
Ulaz
GDGHDCAF#D
5
Izlaz
CGCEGFDHG
Objašnjenje
Pomeranjem od tona G za 5 mesta udesno u odnosu na redosled
C, C#, D, D#, E, F, F#, G, G#, A, A#, H, C, C#, D, D#, E, F, ....
dobija se ton C. Pomeranjem od tona D za 5 mesta udesno dobija se ton G itd.
Primer 2
Ulaz
C#F#AG
-3
18
Izlaz
A#D#F#E
*/
int pronadji(int noteSize, string nota, string note[]) {
// Pretraga
for (int i = 0; i < noteSize; i++) {
if (note[i] == nota) {
return i; // pronadjeno
}
}
return -1; // nije pronadjeno
}
int main() {
string note[] = {"C", "C#", "D", "D#", "E", "F", "F#", "G", "G#", "A", "A#", "H"};
int length = sizeof(note) / sizeof(string);
string melodija;
int pomeraj;
cin >> melodija;
cin >> pomeraj;
for (int i = 0; i < melodija.length(); i++) {
string nota;
if (i + 1 < melodija.size() && melodija.substr(i + 1, 1) == "#") {
nota = melodija.substr(i, 2); // uzmi i povišeni ton
i++; // pomeri se za dodatni karakter
} else {
nota = melodija.substr(i, 1); // uzmi osnovni ton
}
int poz = pronadji(length, nota, note);
if (poz != -1) {
int novaPoz = (poz + length + pomeraj) % length; // transponuj ton
cout << note[novaPoz]; // ispiši transponovani ton
} else {
cout << nota; // ako ton nije pronađen, ispiši ga direktno (ili možeš da obradiš grešku)
}
}
cout << endl; // za novi red posle transponovanja
return 0;
}
using namespace std;
/*
Tonovi se u muzici ređaju po oktavama, koje se sastoje od po 7 osnovnih tonova (bele dirke na klaviru)
i 5 povišenih/sniženih tonova (crne dirke na klaviru). Osnovni tonovi su C, D, E, F, G, A, H, dok se
povišeni/sniženi tonovi nalaze između tonova C i D (to je ton C# tj. D♭), zatim između D i E (to je ton
D# tj. E♭), između F i G (to je ton F# tj. G♭), između G i A (to je ton G# tj. A♭) i između A i H (to je ton A#
tj. H♭, koji se nekada obeležava i sa B). Dogovorimo se da ćemo sve međutonove obeležavati kao povišene
(korišđenjem oznake #). Tada se svi tonovi ređaju na sledeći način:
C, C#, D, D#, E, F, F#, G, G#, A, A#, H, C, C#, D, D#, E, F, ....
Transponovanje neke melodije znači njeno pomeranje za određeni broj tonova naviše ili naniže. Napiši
program koji transponuje unetu melodiju tj. uneti niz tonova.
Opis ulaza
Sa standardnog ulaza se unosi niska od najviše 1000 karaktera koja sadrži niz tonova koje treba transponovati, a zatim i broj između -11 i 11 koji označava za koliko tonova je potrebno transponovati taj niz
tonova.
Opis izlaza
Na standardni izlaz transponovani niz tonova.
Primer 1
Ulaz
GDGHDCAF#D
5
Izlaz
CGCEGFDHG
Objašnjenje
Pomeranjem od tona G za 5 mesta udesno u odnosu na redosled
C, C#, D, D#, E, F, F#, G, G#, A, A#, H, C, C#, D, D#, E, F, ....
dobija se ton C. Pomeranjem od tona D za 5 mesta udesno dobija se ton G itd.
Primer 2
Ulaz
C#F#AG
-3
18
Izlaz
A#D#F#E
*/
int pronadji(int noteSize, string nota, string note[]) {
// Pretraga
for (int i = 0; i < noteSize; i++) {
if (note[i] == nota) {
return i; // pronadjeno
}
}
return -1; // nije pronadjeno
}
int main() {
string note[] = {"C", "C#", "D", "D#", "E", "F", "F#", "G", "G#", "A", "A#", "H"};
int length = sizeof(note) / sizeof(string);
string melodija;
int pomeraj;
cin >> melodija;
cin >> pomeraj;
for (int i = 0; i < melodija.length(); i++) {
string nota;
if (i + 1 < melodija.size() && melodija.substr(i + 1, 1) == "#") {
nota = melodija.substr(i, 2); // uzmi i povišeni ton
i++; // pomeri se za dodatni karakter
} else {
nota = melodija.substr(i, 1); // uzmi osnovni ton
}
int poz = pronadji(length, nota, note);
if (poz != -1) {
int novaPoz = (poz + length + pomeraj) % length; // transponuj ton
cout << note[novaPoz]; // ispiši transponovani ton
} else {
cout << nota; // ako ton nije pronađen, ispiši ga direktno (ili možeš da obradiš grešku)
}
}
cout << endl; // za novi red posle transponovanja
return 0;
}
Prvo je kreiran niz stringova koji predstavljaju note. Korisnik učitava melodiju kao string i pomeraj kao int. Melodija sadrži u sebi note, koje programski treba odrediti. Unutar for petlje se izdvaja nota kao podstring dužine 1 ili podstring dužine 2, ako nota sadrži karakter "#". Za izdvojenu notu se dalje pronalazi njena trenutna pozicija u nizu stringova note i za tu pretragu je kreirana posebna funkcija pod nazivom "pronadji", koja vraća poziciju tekuće note ili, ako je ne nađe, vraća vrednost "-1".
Za pretraživanje je ovde korišćen algoritam linearne pretrage koji neće biti dovoljno efikasan za niz sa velikim brojem podataka.
Da bi se pronašla nova pozicija, potrebno je dodati vrednost pomeraja čija vrednost može biti i negativan ceo broj(pomeranje "u levo").
Ako vrednost pomeraja+stara pozicija prelazi vrednost dužine niza onda se brojanje pozicije nastavlja od početka niza. Isto tako ako se pomeranje pozicije vrši na levu stranu niza, posle pozicije čija je vrednost 0, brojanje se nastavlja sa kraja niza u levo. Ovo se može ostvariti pomoću operatora za izračunavanje modula celog broja "%" na sledeći način:
nova_pozicija = (stara_pozicija+pomeraj) % duzina_niza
Za pretraživanje je ovde korišćen algoritam linearne pretrage koji neće biti dovoljno efikasan za niz sa velikim brojem podataka.
Da bi se pronašla nova pozicija, potrebno je dodati vrednost pomeraja čija vrednost može biti i negativan ceo broj(pomeranje "u levo").
Ako vrednost pomeraja+stara pozicija prelazi vrednost dužine niza onda se brojanje pozicije nastavlja od početka niza. Isto tako ako se pomeranje pozicije vrši na levu stranu niza, posle pozicije čija je vrednost 0, brojanje se nastavlja sa kraja niza u levo. Ovo se može ostvariti pomoću operatora za izračunavanje modula celog broja "%" na sledeći način:
nova_pozicija = (stara_pozicija+pomeraj) % duzina_niza
Da bismo poboljšali rešenje koristeći binarnu pretragu umesto linearne pretrage, potrebno je prvo sortirati niz tonova (što već jeste u ovom slučaju jer su tonovi definisani u redosledu). Nakon toga, možemo implementirati funkciju za binarnu pretragu koja će efikasnije nalaziti pozicije tonova.
Evo kako to može izgledati:
- Linearna vs. Binarna pretraga: U originalnom rešenju se koristi linearna pretraga, što je dovoljno za mali broj tonova, ali se može unaprediti korišćenjem binarne pretrage jer je niz tonova već sortiran. Ovo poboljšava efikasnost, posebno za veće nizove.
- Modulo operator: Važno je naglasiti da modulo operacija u formuli (poz + pomeraj + length) % length omogućava pravilno rukovanje pomerajem, čak i za negativne vrednosti, osiguravajući da se transponovanje vrati na početak niza ako je potrebno.
Evo kako to može izgledati:
Rešenje sa upotrebom nizova i sa linearnom pretragom niza
#include <iostream>
#include <string>
#include <algorithm> // za std::lower_bound
using namespace std;
int pronadji(int noteSize, const string& nota, const string note[]) {
// Koristi se binarna pretraga
const string* found = lower_bound(note, note + noteSize, nota);
if (found != note + noteSize && *found == nota) {
return found - note; // pronadjeno
}
return -1; // nije pronadjeno
}
int main() {
string note[] = {"C", "C#", "D", "D#", "E", "F", "F#", "G", "G#", "A", "A#", "H"};
int length = sizeof(note) / sizeof(string);
string melodija;
int pomeraj;
cin >> melodija;
cin >> pomeraj;
for (int i = 0; i < melodija.length(); i++) {
string nota;
if (i + 1 < melodija.size() && melodija.substr(i + 1, 1) == "#") {
nota = melodija.substr(i, 2); // uzmi i povišeni ton
i++; // pomeri se za dodatni karakter
} else {
nota = melodija.substr(i, 1); // uzmi osnovni ton
}
int poz = pronadji(length, nota, note);
if (poz != -1) {
int novaPoz = (poz + length + pomeraj) % length; // transponuj ton
cout << note[novaPoz]; // ispiši transponovani ton
} else {
cout << nota; // ako ton nije pronađen, ispiši ga direktno (ili možeš da obradiš grešku)
}
}
cout << endl; // za novi red posle transponovanja
return 0;
}
#include <string>
#include <algorithm> // za std::lower_bound
using namespace std;
int pronadji(int noteSize, const string& nota, const string note[]) {
// Koristi se binarna pretraga
const string* found = lower_bound(note, note + noteSize, nota);
if (found != note + noteSize && *found == nota) {
return found - note; // pronadjeno
}
return -1; // nije pronadjeno
}
int main() {
string note[] = {"C", "C#", "D", "D#", "E", "F", "F#", "G", "G#", "A", "A#", "H"};
int length = sizeof(note) / sizeof(string);
string melodija;
int pomeraj;
cin >> melodija;
cin >> pomeraj;
for (int i = 0; i < melodija.length(); i++) {
string nota;
if (i + 1 < melodija.size() && melodija.substr(i + 1, 1) == "#") {
nota = melodija.substr(i, 2); // uzmi i povišeni ton
i++; // pomeri se za dodatni karakter
} else {
nota = melodija.substr(i, 1); // uzmi osnovni ton
}
int poz = pronadji(length, nota, note);
if (poz != -1) {
int novaPoz = (poz + length + pomeraj) % length; // transponuj ton
cout << note[novaPoz]; // ispiši transponovani ton
} else {
cout << nota; // ako ton nije pronađen, ispiši ga direktno (ili možeš da obradiš grešku)
}
}
cout << endl; // za novi red posle transponovanja
return 0;
}
Prelazak sa statičkog niza na vektore donosi nekoliko prednosti. Prvo, vektori u C++ automatski upravljaju veličinom, omogućavajući fleksibilniju manipulaciju podacima. Takođe, funkcija find iz STL-a nudi efikasniji način pretrage tonova nego ručno pretraživanje u statičkom nizu. Koristeći modulo operator (poz + pomeraj + length) % length, omogućavamo ciklično prelaženje kroz tonove, čime osiguravamo da i pri transpozicijama koje izlaze izvan granica niza, tonovi pravilno rotiraju nazad na početak."
Zadatak se može rešiti i upotrebom vektora, što predstavlja poboljšanu verziju rešenja:
Rešenje sa upotrebom vektora
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<string> note = {"C", "C#", "D", "D#", "E", "F", "F#", "G", "G#", "A", "A#", "H"};
string melodija;
int pomeraj;
cin >> melodija;
cin >> pomeraj;
for (int i = 0; i < melodija.length(); i++) {
string nota;
if (i + 1 < melodija.length() && melodija.substr(i + 1, 1) == "#") {
nota = melodija.substr(i, 2); // uzmi povišeni ton
i++; // pomeri se za dodatni karakter
} else {
nota = melodija.substr(i, 1); // uzmi osnovni ton
}
auto it = find(note.begin(), note.end(), nota);
if (it != note.end()) {
int poz = it - note.begin();
int novaPoz = (poz + pomeraj + note.size()) % note.size(); // transponuj ton
cout << note[novaPoz]; // ispiši transponovani ton
} else {
cout << nota; // ako ton nije pronađen, ispiši ga direktno
}
}
cout << endl; // novi red posle transponovanja
return 0;
}
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<string> note = {"C", "C#", "D", "D#", "E", "F", "F#", "G", "G#", "A", "A#", "H"};
string melodija;
int pomeraj;
cin >> melodija;
cin >> pomeraj;
for (int i = 0; i < melodija.length(); i++) {
string nota;
if (i + 1 < melodija.length() && melodija.substr(i + 1, 1) == "#") {
nota = melodija.substr(i, 2); // uzmi povišeni ton
i++; // pomeri se za dodatni karakter
} else {
nota = melodija.substr(i, 1); // uzmi osnovni ton
}
auto it = find(note.begin(), note.end(), nota);
if (it != note.end()) {
int poz = it - note.begin();
int novaPoz = (poz + pomeraj + note.size()) % note.size(); // transponuj ton
cout << note[novaPoz]; // ispiši transponovani ton
} else {
cout << nota; // ako ton nije pronađen, ispiši ga direktno
}
}
cout << endl; // novi red posle transponovanja
return 0;
}