Zadanie z programowania matura 2017

Question

Dzień dobry

Proszę o pomoc z zadaniem 6.3

https://arkusze.pl/maturalne/informatyka-2017-maj-matura-rozszerzona-2.pdf

Nie mam innego pomysłu niż rozpisanie na 9 przypadków, ale w takim wypadku kod jest nadmiernie skomplikowany.  Bo piksel w tablicy może być w jednym z czterech rogów, może nie być w rogu ale być na zewnętrznej krawędzi tablicy, a może być też z każdej strony otoczony innymi pikselami.

Myślałam, żeby pomieszać ify ze switchami. Wyglądałoby to tak. Jeden duży switch, który by się zmieniał w zależności od wiersza i byłyby 3 przypadki - pierwszy wiersz, ostatni i default. W każdym z przypadków wstawiłabym kolejnego switcha tym razem od kolumny i też trzy przypadki - pierwsza kolumna, ostatnia i default. W takim wypadku kod wygląda dużo lepiej, ale wciąż pozostaje problem z ifami.

I nie wiem, czy moje rozumienie problemu jest słuszne. Dwa piksele są kontrastujące jak różnią się o więcej niż 128. I trzeba takie piksele policzyć. Tylko jak? Zakładam, że jeżeli mam iterację numer 1 i piksele numer 1 i 2 ze sobą kontrastują, to liczę piksel numer 1 a numer 2 zostanie policzony osobno w kolejnej iteracji. Funkcja if dla przypadku dziewiątego, czyli kiedy piksel jest otoczony z każdej strony, wygląda tak:

/// j - numer wiersza
/// i - numer kolumny
/// tab[j][i] - dany piksel w tablicy dwuwymiarowej

if ( tab[j][i]-tab[j][i+1]>128 || tab[j][i]-tab[j][i+1]<-128 || tab[j][i]-tab[j][i-1]>128 || tab[j][i]-tab[j][i-1]<-128 || tab[j][i]-tab[j-1][i]>128 || tab[j][i]-tab[j-1][i]<-128 || tab[j][i]-tab[j+1][i]>128 || tab[j][i]-tab[j+1][i]<-128)
ile++;

Jak widać to jest zbyt skomplikowane. Czy da się to jakoś uprościć? Zrobić funkcję? Jeśli tak to jaką?

 

 

Answer 1

Zrób funkcję, która sprawdza czy dany pixel ma sąsiada, z którym kontrastuje.

bool pixelJestKontrastujący(int x, int y, unsigned char *tablica, int szerokosc, int wysokosc) {
    // podczas sprawdzania pixeli musisz uwzględnić pixele znajdujące się na brzegu obrazka
    if (x > 0) {
        // sprawdz lewego sąsiada
    }
    if (x < szerokosc - 1) {
        // sprawdz prawego sąsiada
    }
    if (y > 0) {
        // sprawdz górnego sąsiada
    }
    if (y < wysokosc - 1) {
        // sprawdz dolnego sasiada
    }
    // żaden z sasiadów nie kontrastuje z tym pixelem
    return false;
}

i wywołaj ją w pętli dla wszystkich pixeli

Comments

@tangarr, Ostatnie już pytanie - jak wysłać funkcję dwuwymiarową do funkcji? Na coś tam trzeba było zwrócić uwagę, ale zapomniałam.

---

Rozumiem, że masz na myśli tablicę dwuwymiarową.

Okazało się, że nie mam pomysłu jak to rzutować. W tej chwili widzę tylko dwa rozwiązania:
1. Jako argument funkcji przekazujesz tablicę o konkretnych rozmiarach.
2. Używasz szablonu.

#include <iostream>
#include <string>

using namespace std;

void funkcja1(int tablica[10][20]) {
    cout << __FUNCTION__ << endl;
    for (int i=0; i<10; i++) {
        for (int j=0; j<20; j++) {
            cout << tablica[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

template<int X, int Y>
void funkcja2(int tablica[X][Y]) {
    cout << __FUNCTION__ << endl;
    for (int i=0; i<X; i++) {
        for (int j=0; j<Y; j++) {
            cout << tablica[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int main()
{
    int tablica[10][20];
    for (int i=0; i<10; i++) {
        for (int j=0; j<20; j++) {
            tablica[i][j] = 10*i+j;
        }
    }
    funkcja1(tablica);
    funkcja2<10,20>(tablica);
    return 0;
}

Może ktoś zaproponuje inne rozwiązania.

---

W sensie chodzi mi o Twój pierwszy pomysł, jak to zrobiłeś z unsigned char *, tylko to jest tablica intowa dwuwymiarowa. Jak to zapisać poprawnie? Bo dla jednowymiarowej robi się *(tablica+numer_w_tablicy). Nie muszę całego kodu, tylko jak napisać nazwę tablicy/wskaźnika, jak użyć w funkcji i jak to wywołać, bo resztę to ja umiem.

---

W poprzednim pomyśle popełniłem błąd.
Wskaźnik podwójny by zadziałał, gdyby tablica była alokowana dynamicznie na stercie.

#include <iostream>

using namespace std;

void funkcja(int **tablica, int wiersze, int kolumny) {
    for (int i=0; i<wiersze; i++) {
        for (int j=0; j<kolumny; j++) {
            cout << tablica[i][j] << " ";
        }
        cout << endl;
    }
}

int main()
{
    int licznik = 0;
    int **tablica = new int *[20];
    for (int i=0; i<20; i++) {
        tablica[i] = new int[32];
        for (int j=0; j<32; j++) {
            tablica[i][j] = licznik++;
        }
    }
    
    funkcja(tablica, 20, 32);
    
    // zwalnianie pamięci
    for (int i=0; i<20; i++)
        delete [] tablica[i];
    delete [] tablica;

    return 0;
}

 

---

To ja może jednak zrobię na 4 switche....

Nie chcę Cię męczyć, pogadamy o tym jutro, jeżeli będziesz chciał.

Answer 2

Lecisz sobie po całej tablicy i przy każdym pikselu sprawdzasz jego różnicę z następnym w poziomie i następnym w pionie i tyle...

    int count = 0;
    for (int i= 0; i< 199; i++) {
        for (int j=0; j<319; j++) {
            if (abs(tab[i][j] - tab[i][j+1]) > 128)
                count ++;                    
            if (abs(tab[i][j] - tab[i+1][j]) > 128)
                count ++;                    
        }
    }

 

Comments

Czy do abs potrzebna jest jakaś biblioteka poza iostream i fstream?

---

#include <cmath>

abs jest potrzebny bo nie wiadomo który piksel jest większy

---

@manjaro,
Twoje rozwiązanie nie jest do końca poprawne, dla danych z pliku "przyklad.txt" obliczaną wartością (przy użyciu takiej pętli) będzie liczba 4 zamiast 5.

 

 

---

Rzeczywiście, mój błąd. Zliczałem tylko pary, a nie punkty.

Tutaj macie prawidłowe rozwiązanie w Pythonie, myślę że łatwo przerobicie na C++

tab = []
file = open('przyklad.txt', 'r')
for line in file:
    tab.append(line.split())
file.close()

result = []
for i in range(119):
    for j in range(319):
        if abs(int(tab[i][j]) - int(tab[i][j+1])) > 128:
            if [i,j] not in result:
                result.append([i,j])
            if [i,j+1] not in result:
                result.append([i,j+1])

        if abs(int(tab[i][j]) - int(tab[i+1][j])) > 128:
            if [i,j] not in result:
                result.append([i,j])
            if [i+1,j] not in result:
                result.append([i+1,j])

print(len(result))

 

---

A tu cały kod programu w C++

#include <iostream>
#include <set>
#include <fstream>

int cnt(int tab[][320]) {
    std::set<std::pair<int, int>> result;
    for (int i= 0; i< 199; i++) {
        for (int j=0; j<319; j++) {
            if (abs(tab[i][j] - tab[i][j+1]) > 128) {
                result.emplace(i,j);
                result.emplace(i,j+1);
            }
            if (abs(tab[i][j] - tab[i+1][j]) > 128) {
                result.emplace(i,j);
                result.emplace(i+1,j);
            }
        }
    }
    return result.size();
}

int main(){
    int tab[200][320];
    std::fstream file;
    std::string filename;
    filename = "przyklad.txt";
    file.open(filename.c_str());

    for (int i=0; i<200; i++) {
       for (int j=0; j<320; j++) {
           file >> tab[i][j];
        }
    }
    file.close();
    std::cout << cnt(tab);
}

 

Answer 3

Poniżej przykład napisany w C++17 w którym wyliczana jest liczba pikseli kontrastujących.

#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>

using namespace std;

constexpr int column {320};
constexpr int diff {128};

class Pixel
{
    int value {0};
    bool has_high_contrast {false};
    void tagContrast(){ if( !has_high_contrast ) { has_high_contrast=true ; ++Pixel::result; }; };

public:

    friend istream& operator>>( istream &is , Pixel &pixel )
    {
        return is >> pixel.value;
    }

    bool operator^( Pixel& pixel )
    {
        if( abs(value-pixel.value)>diff )
        {
            tagContrast();
            pixel.tagContrast();
            return true;
        }
        return false;
    }

    inline static int result {0};
};

auto transform_xy( int i , int column )
{
    auto y {i/column};
    auto x {i-y*column};
    return make_pair(x,y);
}

int main()
{
    ifstream file {"dane.txt"};
    vector<Pixel> pixels { istream_iterator<Pixel>{file} , {} };

    auto row { static_cast<int>(pixels.size())/column };
    for( size_t index {0} ; index < pixels.size() ; ++index )
    {
        auto [x,y] = transform_xy(index,column);

        if( x+1 <  column ) pixels[index]^pixels[x+1+y*column];
        if( y+1 <  row    ) pixels[index]^pixels[x+(y+1)*column];
    }

    cout << Pixel::result << endl;

    return 0;
}

 

Comments

Pytanie á propos tego kodu - rozumiem, że to co się dzieje przy vectorze pixels, to wrzucenie do niego contentu z pliku file poprzez istream_iterator, ale:

• Czy tutaj nie powinien zostać użyty konstruktor? (5)
• Rozumiem, że ten direct initialization tam automatycznie tworzy istream_iterator<Pixel>() (tzn. EOS)?

---

Czy tutaj nie powinien zostać użyty

Tutaj został użyty konstruktor std::vector.

vector<Pixel> pixels { istream_iterator<Pixel>{file} , {} };
// jest tym samym co
vector<Pixel> pixels( istream_iterator<Pixel>{file} , {} );

Rozumiem, że ten direct initialization tam automatycznie tworzy ...

Dokładnie, kompilator dedukuje typ istream_iterator<Pixel>() na podstawie pierwszego parametru.

BTW, proces wczytywania wartości z pliku można skrócić do jednej linijki, używając do tego funkcji szablonowej lvalue

template <typename T>
inline constexpr remove_reference_t<T> &lvalue(T &&value) noexcept
{
    return static_cast<remove_reference_t<T> &>(value);
}

vector<Pixel> pixels { istream_iterator<Pixel>{lvalue(ifstream{"dane.txt"})} , {} };