• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Optymalizacja kodu

VPS Starter Arubacloud
0 głosów
157 wizyt
pytanie zadane 21 stycznia 2022 w C i C++ przez BKantur Nowicjusz (160 p.)

Witam,

stworzyłem działający kod który przyjmuje zbiór o mocy n, i liczbę k który ma znaleźć najmniejszą liczbę nienależącą do zbioru i podzielną przez k.  Jednak nie mieści się on w ramach czasowych zadania i chciałbym się dowiedzieć jak mogę go zoptymalizować. Oto wspomniany kod:

#include <bits/stdc++.h>
using namespace std;
vector <long long> vec;
int n;

bool isit(long long l)
{
    for (int i=0;i<n;i++)
    {
        if (l==vec[i])
        return 1;
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    long long k,a,l=1;

    cin>>n>>k;

    for(int j=0;j<n;j++)
    {
        cin>>a;
        vec.push_back(a);
    }
    int i=1;
    while(true)
    {
        l=k*i;

        if (isit(l)==0)
        {
            cout<<l;
            return 0;
        }
        i++;
    }
}

 

komentarz 21 stycznia 2022 przez TOM_CPP Pasjonat (22,640 p.)

znaleźć najmniejszą liczbę nienależącą do zbioru i podzielną przez k

Przy założeniu że dziedziną jest zbiór liczb całkowitych i dany zbiór o mocy n jest skończony, to taka liczba nie istnieje.

 

 

komentarz 21 stycznia 2022 przez Wiciorny Ekspert (269,120 p.)
dowód: n +1 nie należy do zbioru i indykcyjnie da się to dowieść że istnieje taka liczba, ergo- zbiór jest skończony więc n+1 istnieje.
Autorowi albo brakuje faktu, że zbiór jest ograniczony od góry przez podaną wartość, albo że mowa "w dziedzinie jakiejs funkcji"
1
komentarz 21 stycznia 2022 przez adrian17 Ekspert (344,100 p.)
...o czym Wy mówicie? Dość jasnym jest że autorowi chodzi o

zbiór: 1 2 3 4 5 6 7 8
k: 5
najmniejsza liczba podzielna przez k ale nie będąca w zbiorze: 10
komentarz 21 stycznia 2022 przez TOM_CPP Pasjonat (22,640 p.)

najmniejsza liczba podzielna przez k ale nie będąca w zbiorze: 10

Założyłeś że mamy tutaj do czynienia z liczbami naturalnymi. Autor nigdzie o tym nie wspomniał.

komentarz 21 stycznia 2022 przez Wiciorny Ekspert (269,120 p.)
bo autor nie do precyzował tak mi się wydaje, samo zadanie brzmi niepełnie. w kwestii zbioru i zakresu np. dla liczby ograniczającej zbiór n

1 odpowiedź

0 głosów
odpowiedź 21 stycznia 2022 przez adrian17 Ekspert (344,100 p.)
Hint: nie musisz dla każdej wielokrotności iterować się po całym zbiorze. Możesz zbiór albo posortować, albo... zamienić go na "prawdziwy" C++owy zbiór std::unordered_set i sprawdzać czy w nim jest.

Możesz też w trakcie wczytywania zbioru od razu przetwarzać tylko liczby podzielne przez k i zignorować resztę.

Podobne pytania

0 głosów
2 odpowiedzi 382 wizyt
pytanie zadane 2 października 2021 w C i C++ przez Michał F Nowicjusz (120 p.)
0 głosów
1 odpowiedź 120 wizyt
0 głosów
1 odpowiedź 205 wizyt

92,452 zapytań

141,262 odpowiedzi

319,085 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...