Skocz do zawartości

  • 👋 Witaj na MPCForum!

    Przeglądasz forum jako gość, co oznacza, że wiele świetnych funkcji jest jeszcze przed Tobą! 😎

    • ✅ Pełny dostęp do działów i ukrytych treści
    • ✅ Możliwość pisania i odpowiadania w tematach
    • ✅ System prywatnych wiadomości
    • ✅ Zbieranie reputacji i rozwijanie swojego profilu
    • ✅ Członkostwo w jednej z największych społeczności graczy

    👉 Dołączenie zajmie Ci mniej niż minutę – a zyskasz znacznie więcej!

    Zarejestruj się teraz

C++ Zadanie

.Bumek662.

Rekomendowane odpowiedzi

.Bumek662. Specjalista

.Bumek662.

Opublikowano
Specjalista

.Bumek662.

Opublikowano

 

 

4GwFiKy.png

 

 

 

Teoretycznie je zrobilem, a praktycznie dostalem za nie tylko 1/2 możliwych pkt. bo działa po prostu za wolno, zresztą zdaję sobie sprawę że można to zrobić lepiej innym sposobem lecz nie mam pomysłu.

#include <iostream>
 
using namespace std;
int results[10000000], amount;
 
int main(){
string text, text2;
while(text != "**"){
    text2 = ""; text = "";
    cin >> text;
    for(int i = text.size()-1; i>=0; i--){
        text2 = text2 + text[i];
    }
    if(text == text2 && text != "**"){
        results[amount] = 1;
        amount ++;
    }else if(text != text2 && text != "**"){
        results[amount] = 0;
        amount ++;
    }
 
}
for(int i = 0; i<amount; i++){
    if(results[i] == 1){
        cout << "TAK" << endl;
    }else{
        cout << "NIE" << endl;
    }
}
 
return 0;
}

Hello there.

Sopelek997 Weteran

Sopelek997

Opublikowano
Weteran

Sopelek997

Opublikowano

1. Czy masz pewność co do maksymalnej liczby podanych wyrazów? Jeśli nie to musisz użyć jakiejś dynamicznej tablicy - najlepiej std::vector.

2. Mała uwaga. Twoja tablica ma 40MB przy kompilacji do 32 bitowej aplikacji. Gdyby była zmienną lokalna to mogłaby się nie zmieścić na stosie. Mógłbyś okazjonalnie dostać błąd spowodowany przepełnieniem stosu.

3. Masz niezainicjalizowaną zmienną amount. To jest prawdopodnie źródło problemu.

4.Wąskim gardłem (pomijając operacje wejścia wyjścia, które w razie potrzeby możesz zastąpić tymi z cstdio) jest ten fragment

for(int i = text.size()-1; i>=0; i--){
    text2 = text2 + text[i];
}

bo konieczne jest wielokrotne zwiększanie rozmiaru stringa, do czego konieczna jest realokacja.

Jako, że znacz maksymalny rozmiar słowa, to zarezerwuj odpowiednią ilość miejsca w stringu (obu stringach w tym przypadku) przed pętlą (std::string::reserve), a pod koniec pętli wywołuj std::string::clear na tym stringu. W dodatku skorzystaj z operatora += zamiast oddzielnie + i =. W tym przypadku będzie duża różnica, bo aktualnie tworzona jest kopia i dopiero ona jest przypisywana.

5. Zamiast pętli while z warunkiem stwórz nieskończoną pętlę i zaraz po wczytaniu stringa porównaj jego wartość z "**" i wtedy decyduj czy wyjść z pętli.

6.

To

if(text == text2 && text != "**"){
results[amount] = 1;
amount ++;
}else if(text != text2 && text != "**"){
results[amount] = 0;
amount ++;
}

jako, że masz powtarzającą się linię kodu można zapisać:

if(text == text2 && text != "**"){
results[amount] = 1;
}else if(text != text2 && text != "**"){
results[amount] = 0;
}
amount ++;

Dodatkowo po zastosowaniu się do punktu 5. nie będzie konieczny drugi warunek:

if(text == text2){
results[amount] = 1;
}else{
results[amount] = 0;
}
amount ++;

Najprościej jednak będzie

results[amount++] = (text == text2);

7. Staraj się nie korzystać ze zmiennych globalnych.

8. Używaj preinkrementacji jeśli jest to możliwe (np przy iterowaniu zmiennej w pętli). Gdyby twoje 'i' to był iterator to w niektórych przypadkach mogłaby być różnica w wydajności.

9. Jeśli możesz korzystać z biblioteki algorithm to można ten kod napisać tak

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> results;
    results.reserve(10000000); //nie zaszkodzi
    std::string text;
    text.reserve(200); //maksymalny rozmiar tekstu
    int count = 0;
    for(; //idiomatyczna nieskonczona petla
    {
        std::cin >> text;
        if(text == "**") break;
        results[count++] = std::equal(text.begin(), text.end(), text.rbegin()); //z algorithm
        text.clear();
    }
    for(int i = 0; i < count; ++i)
    {
        std::cout << (results[i] ? "TAK" : "NIE") << '\n';
    }

    return 0;
}
981841412442977292370.png
.Bumek662. Specjalista

.Bumek662.

Opublikowano
Specjalista

.Bumek662.

  • Autor
Opublikowano

 

1. Czy masz pewność co do maksymalnej liczby podanych wyrazów? Jeśli nie to musisz użyć jakiejś dynamicznej tablicy - najlepiej std::vector.

2. Mała uwaga. Twoja tablica ma 40MB przy kompilacji do 32 bitowej aplikacji. Gdyby była zmienną lokalna to mogłaby się nie zmieścić na stosie. Mógłbyś okazjonalnie dostać błąd spowodowany przepełnieniem stosu.

3. Masz niezainicjalizowaną zmienną amount. To jest prawdopodnie źródło problemu.

4.Wąskim gardłem (pomijając operacje wejścia wyjścia, które w razie potrzeby możesz zastąpić tymi z cstdio) jest ten fragment

for(int i = text.size()-1; i>=0; i--){
    text2 = text2 + text[i];
}

bo konieczne jest wielokrotne zwiększanie rozmiaru stringa, do czego konieczna jest realokacja.

Jako, że znacz maksymalny rozmiar słowa, to zarezerwuj odpowiednią ilość miejsca w stringu (obu stringach w tym przypadku) przed pętlą (std::string::reserve), a pod koniec pętli wywołuj std::string::clear na tym stringu. W dodatku skorzystaj z operatora += zamiast oddzielnie + i =. W tym przypadku będzie duża różnica, bo aktualnie tworzona jest kopia i dopiero ona jest przypisywana.

5. Zamiast pętli while z warunkiem stwórz nieskończoną pętlę i zaraz po wczytaniu stringa porównaj jego wartość z "**" i wtedy decyduj czy wyjść z pętli.

6.

To

if(text == text2 && text != "**"){
results[amount] = 1;
amount ++;
}else if(text != text2 && text != "**"){
results[amount] = 0;
amount ++;
}

jako, że masz powtarzającą się linię kodu można zapisać:

if(text == text2 && text != "**"){
results[amount] = 1;
}else if(text != text2 && text != "**"){
results[amount] = 0;
}
amount ++;

Dodatkowo po zastosowaniu się do punktu 5. nie będzie konieczny drugi warunek:

if(text == text2){
results[amount] = 1;
}else{
results[amount] = 0;
}
amount ++;

Najprościej jednak będzie

results[amount++] = (text == text2);

7. Staraj się nie korzystać ze zmiennych globalnych.

8. Używaj preinkrementacji jeśli jest to możliwe (np przy iterowaniu zmiennej w pętli). Gdyby twoje 'i' to był iterator to w niektórych przypadkach mogłaby być różnica w wydajności.

9. Jeśli możesz korzystać z biblioteki algorithm to można ten kod napisać tak

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> results;
    results.reserve(10000000); //nie zaszkodzi
    std::string text;
    text.reserve(200); //maksymalny rozmiar tekstu
    int count = 0;
    for(; //idiomatyczna nieskonczona petla
    {
        std::cin >> text;
        if(text == "**") break;
        results[count++] = std::equal(text.begin(), text.end(), text.rbegin()); //z algorithm
        text.clear();
    }
    for(int i = 0; i < count; ++i)
    {
        std::cout << (results[i] ? "TAK" : "NIE") << '\n';
    }

    return 0;
}

Jak dzialaja te wektory?

Co daje to .reserve, oraz co daje biblioteka alghoritm?

 

Twoj kod uzyskal najlepszy wynik, lecz nie pelny:

 

http://prntscr.com/90lzod

 

wyskoczyl 2x limit czasu

Hello there.

Sopelek997 Weteran

Sopelek997

Opublikowano
Weteran

Sopelek997

Opublikowano

http://en.cppreference.com/w/cpp/container/vector

http://en.cppreference.com/w/cpp/header/algorithm

 

to trzeba zmienić sposób w jaki wykonywane są operacje wejścia wyjścia.

981841412442977292370.png
Gość

Gość

Opublikowano

Gość

Opublikowano

Niepotrzebnie porównujecie cały tekst - wystarczy tylko połowę

Gość

Gość

Opublikowano

Gość

Opublikowano

zmodyfikowana wersja sopelka:

 

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> results;
    results.reserve(10000000); //nie zaszkodzi
    std::string text;
    text.reserve(200); //maksymalny rozmiar tekstu
    int count = 0;
    for(; //idiomatyczna nieskonczona petla
    {
        std::cin >> text;
        if(text == "**") break;
        results[count++] = std::equal(text.begin(), text.begin() + text.size()*0.5, text.rbegin()); //z algorithm
        text.clear();
    }
    for(int i = 0; i < count; ++i)
    {
        std::cout << (results[i] ? "TAK" : "NIE") << '\n';
    }

    return 0;
}

i coś tam w necie poszperałem

.Bumek662. Specjalista

.Bumek662.

Opublikowano
Specjalista

.Bumek662.

  • Autor
Opublikowano

zmodyfikowana wersja sopelka:

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> results;
    results.reserve(10000000); //nie zaszkodzi
    std::string text;
    text.reserve(200); //maksymalny rozmiar tekstu
    int count = 0;
    for(; //idiomatyczna nieskonczona petla
    {
        std::cin >> text;
        if(text == "**") break;
        results[count++] = std::equal(text.begin(), text.begin() + text.size()*0.5, text.rbegin()); //z algorithm
        text.clear();
    }
    for(int i = 0; i < count; ++i)
    {
        std::cout << (results[i] ? "TAK" : "NIE") << '\n';
    }

    return 0;
}

i coś tam w necie poszperałem

nadal limit czasu :P

Hello there.

Zarchiwizowany

Ten temat przebywa obecnie w archiwum. Dodawanie nowych odpowiedzi zostało zablokowane.

Tematy
×
×
  • Dodaj nową pozycję...