Question

Un numar natural cu cel putin 2 cifre se numeste 2-ordonat daca toate cifrele sale sunt in ordine crescatoare si valoarea absoluta a diferentei dintre oricare doua cifre aflate pe pozitii consecutive este egala cu 2.
EX: numarul 2468 este 2-ordonat, dar numarul 131 nu este 2-ordonat .
se cere scrierea in fisierul BAC.TXT a tuturor numerelor naturale 2-ordonate. Fiecare numar este scris pe cate o linie a fisierului.
Pentru determinareanumerelor cerute se utilizeaza un algoritm eficient din punctul de vedere al timpului de executare.
A. descrieti in limbajul natural algoritmul utilizat , justificand eficienta acestuia.
B. scrieti programul C/C++ corespunzator algoritmului descris

Answer 1

1) Daca sunt valori de doua intre numere consecutive atunci o sa fie subsiruri ale cifrelor impare si cifre pare
2,4,6,8
1,3,5,7,9
O metoda eficienta este sa formezi numarul cu lungime din ce in ce mai mare si sa afisezi toate subsirurile sale de forma:
24 246 46 2468 468 68(observi ca se impart numerele cu mai mult de 3 cifre la puteri ale lui 100 astfel incat resturile sunt aratate)
Algoritmul acesta e eficient pentru ca parcurgi fiecare lista o singura data deci au complexitatea O(2n)
b)
#include <iostream>
#include <cmath>
#include <conio.h>
using namespace std;

int main(){
int cifre_pare[4]={2,4,6,8},cifre_impare[5]={1,3,5,7,9},i,mult100=1,nr,subdiv,rang;
nr=cifre_pare[0];

for(i=1;i<4;i++){
nr=nr*10+cifre_pare[i];
cout<<nr<<" ";
subdiv=nr;
rang=i;
while(subdiv/100>0){
subdiv=subdiv%(int)pow(10,rang);
cout<<subdiv<<" ";
rang--;
}
}
nr=cifre_impare[0];
cout<<endl;
for(i=1;i<5;i++){
nr=nr*10+cifre_impare[i];
cout<<nr<<" ";
subdiv=nr;
rang=i;
while(subdiv/100>0){
subdiv=subdiv%(int)pow(10,rang);
cout<<subdiv<<" ";
rang--;
}
}
return 0;
}