Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Cel mai mic număr cu suma cifrelor N în C++

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Dându-se un număr natural n, vrem să găsim cel mai mic număr natural cu proprietatea că suma cifrelor sale este egal cu n.

Exemplu: Pentru n = 13, răspunsul este 49, cu 4 + 9 = 13 = n.

Algoritm naiv

Un algoritm naiv parcurge toate numerele începând cu 1, verificând pentru fiecare în O(lg(n)) dacă suma cifrelor sale este egală cu n:

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim
    int n;
    cin >> n;

    //Căutăm răspunsul
    int i = 1;
    while(true) {
        int copie = i, sumacif = 0;
        while(copie > 0) { //Calculăm suma cifrelor numărului curent, i
            sumacif = sumacif + copie % 10;
            copie = copie / 10;
        }
        if(sumacif == n) { //Am găsit primul număr cum suma cifrelor egală cu n, ne oprim
            cout << i;
            break;
        }
        i++;
    }
    return 0;
}

Algoritm eficient

Să analizăm cum putem să determinăm cel mai mic număr cu suma cifrelor n. Numărul trebuie:

  • să aibă cât mai puține cifre;
  • primele cifre ale sale să fie cât de mici posibile.

Pentru ca numărul să aibă cât mai puține cifre, trebuie să găsim cifre care să scadă rapid valoarea lui n. Astfel, este clar că ultimele cifre ale răspunsului vor fi cifre de 9, până când nu se mai poate. Diferența rămasă va determina prima cifră a lui răspunsului.

Mai exact, dacă n : 9 = x rest y, mai precis n = 9x + y (prin teorema împărțirii cu rest), atunci numărul răspuns are prima cifră egală cu y, iar următoarele x cifre egale cu 9.

Cu această logică, putem să rezolvăm problema astfel:

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim
    int n, raspuns = 0;
    cin >> n;

    //Prima cifră a lui raspuns
    raspuns = n % 9; //n % 9 este y-ul nostru de mai devreme
    for(int i = 1; i <= n / 9; i++) { //n / 9 este x-ul nostru de mai devreme
        raspuns = raspuns * 10 + 9;
    }

    //Afișăm răspunsul
    cout << raspuns;
    return 0;
}

Algoritmul acesta are complexitatea O(n / 9) = O(n).

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

Vectori de frecvență (de apariții) în C++Divide et Impera (metodă de programare C++)Cea mai lungă secvență de elemente crescătoare în C++Ce înseamnă variabilă globală și locală în C++?Șirul lui Fibonacci în C++Verifică dacă un număr este par sau impar fără modulo în C++Rădăcina cubică a unui număr în C++ (cube root)Numărul de cifre ale factorialului unui numărMaximul și minimul a două valori în C++CMMMC a două numere în C++ (cel mai mic multiplu comun)Aria unui triunghi folosind coordonatele acestora în C++Matrice pătratice în C++. Diagonala principală și secundarăCel mai frecvent element dintr-un șir în C++Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicValoarea absolută (modulul) unui număr în C++Citirea și afișarea matricelor în C++Instrucțiunea break (structuri repetitive)Numărul minim de peroane pentru o gară în C++Complexitatea unui algoritm (timp și spațiu) în C++Inversarea unui vector în C++Suma divizorilor unui număr în C++Suma numerelor naturale dintr-un interval dat în C++Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Al N-lea termen dintr-o progresie geometricăNumărul combinărilor în C++ (formula combinărilor)Numărul aranjamentelor în C++ (formula aranjamentelor)Transformarea unei litere mici în literă mare în C++Oglinditul recursiv al unui număr în C++Maximul și minimul a n valori în C++Maximul și minimul unui vector în C++Numărul de apariții al unui număr într-un vector în C++Numărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Oglinditul unui număr în C++Transformarea unei litere mari în literă mică în C++Codul ASCII (tabel complet)Află secolul unui an citit de la tastatură în C++Cel mai mic număr cu suma cifrelor N în C++Numărul de divizori al unui număr în C++Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorInversarea unui șir de caractere în C++Verificare număr prim în C++ (Clasa a IX-a)Numere triunghiulare. Verificarea unui număr triunghiularCâte numere naturale sunt într-un interval dat? (C++)Verifică dacă o literă este vocală în C++Combinatorică în C++: permutări, aranjamente, combinări și alteleVerifică dacă un caracter este literă în C++Transformarea unui număr din baza 2 în baza 10 în C++Factorialul unui număr în C++Cifra maximă a unui număr recursiv în C++Materia pentru olimpiada de informatică - tot ce trebuie să știiCiurul lui Eratostene în C++Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidăAl N-lea termen Fibonacci în C++Vectorii în C++: citire și afișareSuma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Cum să citești și să afișezi în fișiere în C++Funcții în C++. Ce sunt subprogrameleInstrucțiunea do while (structuri repetitive)Verificarea unui an bisect în C++Copiuțe: Cifrele unui numărCel mai mare divizor comun (CMMDC) a două numere în C++Instrucțiunea continue (structuri repetitive)Aria și circumferința unui cerc în C++Suma elementelor unui vector recursiv în C++Cifra de control a unui numărAl N-lea termen dintr-o progresie aritmeticăAlgoritm recursiv pentru căutare binară (clasa a X-a)Instrucțiunea while (structuri repetitive)Afișarea elementelor unui vector recursiv în C++Generarea șirului Fibonacci generalizat în C++Operații cu numere mari în C++ - Toate funcțiile explicateMatrice în C++. Declararea și parcurgerea tablourilor bidimensionaleAflarea sumei primelor N sume GaussMediana unui șir de valori în C++Tipul struct în C++. Ce sunt structurile de date neomogeneInstrucțiunea de decizie în C++: if, else, switch, caseRecursivitate în C++Calculul combinărilor de n luate câte k (nCk) în C++Afișarea divizorilor primi ai unui număr în C++Vectorii în C++: declarare și parcurgereSortare crescătoare recursivă în C++ - Merge sort și Bubble sortȘiruri de caractere în C++. Tot ce trebuie să știiCel mai semnificativ bit în C++Verificare dacă un număr este palindrom în C++Prima cifră a unui număr în C++Verifică dacă o literă este mică sau mare în C++Comentarii în C++Cum să calculezi instant 2 la puterea N în C++De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Cum să afișezi partea întreagă a unui număr real în C++Cifra maximă și minimă a unui număr în C++Verificare dacă șir de caractere este palindrom în C++Pointer în C++. Variabile de tipul char * (char steluță)Tipuri de date în C++: numere întregi, reale, caractere și alteleSuma 1 + 2 + 3 + ... + N în C++Citește un șir de caractere cu spații în C++Distanța dintre două puncte în C++Verifică dacă un caracter este cifră în C++Ce este o variabilă unsigned în C++?CMMDC recursiv a două numere naturale în C++Verifică dacă un număr aparține șirului Fibonacci în C++Transformarea unui număr din baza 10 în baza 2 în C++Numărul permutărilor în C++ (formula permutărilor)Maximul și minimul a trei valori în C++Interschimbarea a două variabile în C++ (3 metode)Structuri repetitive (while, do while, for, etc)Ce înseamnă endl în C++?Indicatorul lui Euler în C++Do while vs while în C++ - Care e diferența?Verifică dacă un număr dat este o putere de 2 în C++Ce este o funcție void în C++?Radicalul unui număr în C++ (rădăcina pătrată)Interclasarea a doi vectori în C++Instrucțiunea for (structuri repetitive)Funcții predefinite în C++ (matematice, șiruri de caractere)Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Bordarea unei matrice în C++Verifică dacă trei puncte sunt coliniare C++Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Cel mai puțin semnificativ bit în C++Căutare binară în C++Numărul de divizori primi ai unui număr în C++

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont