Problema Numere Frumoase

4
  • Publicat de
  • în Fără categorie
  • — 9 oct., 2009 at 4:21 pm

Numerele frumoase sunt numerele care au ca factori primi doar pe 2, 3 si 5. Sirul numerelor frumoase este: 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 16, 18, 20, 24, 25 etc.

Fie n un numar natural dat (n<=1500), afisati pe ecran primele n numere frumoase.

n=16

Numere frumoase: 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 16, 18, 20, 24, 25 .

  • Solutie

Daca analizam problema, putem constata ca orice numar din sir, incepand cu al doilea, se poate obtine inmultind cu 2, 3 sau 5 un numar anterior din sir. Notam cu n2 cel mai mic multiplu de 2 din sir, inca neadaugat, iar cu i indicele din tablou care contine elementul care s-a obtinut prin inmultire cu 2. Vom nota cu n3 cel mai mic multiplu de 3 si indicele j, apoi cu n5 cel mai mic multiplu de 5 si indicele k. Vom adauga numerele pe rand intr-un vector a.

#include <iostream>
using namespace std;
int main()
{
int t=1,n2=2,n3=3,n5=5,i=1,j=1,k=1,l=1,n,a[2000];
cout<<"Dati n: ";cin>>n;
a[1]=1;
while (l<n)
{
if (n2<=n3)
if (n2<=n5) t=n2;
else t=n5;
else if (n3<=n5) t=n3;
else t=n5;
l++;
a[l]=t;
if (t==n2) n2=2*a[++i];
if (t==n3) n3=3*a[++j];
if (t==n5) n5=5*a[++k];
}
for (i=1;i<=l;++i)
cout<<a[i]<<" ";
return 0;
}

Problema provine de la concursul ACM New Zeeland din 1990.

Etichete:

— Albulescu Cosmina a scris 223 articole

Nu există o descriere a autorului.

4 Comentarii

  1. Leocrux spune:
    octombrie 9, 2009 la 6:53 pm

    Bun… 🙂 mi-am dat seama de la inceput ca trebuie sa inmultesti „ceva” cu 2 3 sau 5…insa am sarit prea repede la solutie 😀

  2. mara spune:
    ianuarie 2, 2011 la 2:11 pm

    numarul 11 (dupa cum rezulta din exemplul de mai sus) este numar frumos?

  3. Nicu spune:
    februarie 21, 2012 la 2:55 pm

    #include
    int main()
    {
    int n;
    cin>>n;
    int frumoase=0, i, contor=0, div, x, divizori[100], k;
    for(i=1; i<=2000; i++)
    {
    k=0;
    contor=0;
    x=i;
    while(x!=1)
    {
    for(div=2; div<=x; div++)
    {
    if(x%div==0)
    {
    divizori[k]=div;
    k++;
    x=x/div;
    break;
    }
    }
    }

    for(int j=0; j<k; j++)
    {
    if(divizori[j]!=2 && divizori[j]!=3 && divizori[j]!=5)
    contor++;
    }
    if(contor==0)
    {
    cout<<i<<" ";
    frumoase++;
    }
    if(frumoase==n)
    break;
    }

    }

    Asta e solutia mea, insa nu cred ca 11 este numar frumos.

  4. Ecaterina spune:
    aprilie 5, 2013 la 11:43 am

    Aceste numere frumoase au legătură cu platonicianul arithmos ideon? Mulțumesc