C++ Bc. 45 cpp

Z GeoWikiCZ
Skočit na navigaci Skočit na vyhledávání

Algoritmus 1

#include <iostream>

bool hamming(int n)           // 1 2 3 4 5 6 8 9 10 12 15 ...
{
  while (n%2 == 0) n/=2;
  while (n%3 == 0) n/=3;
  while (n%5 == 0) n/=5;

  return n == 1;
}

int main()
{
  const int N = 1500;
  int n       = 1;
  int h       = 1;
  int pocet   = 1;

  while (pocet < N)
    {
      n++;
      if (hamming(n))
	{
	  h = n;
	  pocet++;
	  // std::cout << h << " ";
	}
    }

  std::cout << N <<  "-te Hammingovo cislo je " << h << "\n";
}

Algoritmus 2

#include <iostream>
#include <algorithm>

void hamming(int h[], int N)  // 1 2 3 4 5 6 8 9 10 12 15 ...
{
  h[0] = 1;                   // prvni Hammingovo cislo;
  int pocet = 1;

  int i2 = 0;
  int i3 = 0;
  int i5 = 0;

  int h2, h3, h5, hn;

  while (pocet < N)
    {
      h2 = h[i2]*2;           // kandidati na nasledujici cislo v posloupnosti
      h3 = h[i3]*3;
      h5 = h[i5]*5;

      hn = std::min(h2, h3);
      hn = std::min(h5, hn);  // hn je nejmensi z cisle h2, h3, h5

      if (hn == h2) i2++;
      if (hn == h3) i3++;
      if (hn == h5) i5++;

      h[pocet++] = hn;
      // std::cout << hn << " ";
    }
}

int main()
{
  const int N = 1500;
  int h[N]; 
  hamming(h, N);

  std::cout << N << "-te Hammingovo cislo je " << h[N-1] << "\n";
}

[ Zpět ]