Пример 2. Решето Эратосфена

13 5 7 43 17 29 11 41

123 13 5 7 43 17 29 11 33 41

43 17 29 11 41

7 17 29 11 41

5 17 29 11 41

13 17 29 11 41

7 43 29 11 41

5 43 29 11 41

13 43 29 11 41

5 7 29 11 41

13 7 29 11 41

13 5 29 11 41

7 43 17 11 41

5 43 17 11 41

13 43 17 11 41

5 7 17 11 41

13 7 17 11 41

13 5 17 11 41

5 7 43 11 41

13 7 43 11 41

13 5 43 11 41

13 5 7 11 41

7 43 17 29 41

5 43 17 29 41

13 43 17 29 41

5 7 17 29 41

13 7 17 29 41

13 5 17 29 41

5 7 43 29 41

13 7 43 29 41

13 5 43 29 41

13 5 7 29 41

5 7 43 17 41

13 7 43 17 41

13 5 43 17 41

13 5 7 17 41

13 5 7 43 41

7 43 17 29 11

5 43 17 29 11

13 43 17 29 11

5 7 17 29 11

13 7 17 29 11

13 5 17 29 11

5 7 43 29 11

13 7 43 29 11

13 5 43 29 11

13 5 7 29 11

5 7 43 17 11

13 7 43 17 11

13 5 43 17 11

13 5 7 17 11

13 5 7 43 11

5 7 43 17 29

13 7 43 17 29

13 5 43 17 29

13 5 7 17 29

13 5 7 43 29

13 5 7 43 17

123 13 5 7 43 17 29 11 33 41

29 11 33 41

123 13 5 7 43 17

If (p)

If (p)

Do

Рассмотрим алгоритм генерации k-элементных подмножеств множества из n элементов, т.е. последовательного формирования возрастающих по значению битовых строк с k единицами.

Пример 1.

И т.д.

..................

.... 000... 1000111

.... 000... 0111100

..................

.... 000.... 100010

.... 000....100001

....000....100000

....000.... 011111

................

....000.... 000011

....000.... 000010

....000....000001

..........

}

В этом алгоритме последовательно получаемые подмножества могут сильно отличаться друг от друга: после (n-1)-элементного множества (которому соответствует число 01111…..1) идёт одноэлементное множество(отвечающее числу 1000……0). Это часто неудобно.

//Nelset.cpp k-элементные подмножества,

// маска - слово

#include <iostream>

#include <fstream>

#include <iomanip>

#include <math.h>

using namespace std;

//Дана совокупность не более n целых чисел

//и число k. Выбрать все подмножества из k

// простых чисел.

//Все подмножества (k – элементные) записать в файл.

const int L=32; // n=31 элемент +1

ifstream fin;

ofstream fout;

// прототипы функций

void print (ofstream &fout, int a[], int n, unsigned int b);

bool prost (int a);

int main ()

{int i;

unsigned int b,n,k, nn;

int a[L];

fin.open("danN_el.txt");

if (fin.fail()){cout<<"error open danN.txt\n"; return(1);}

fout.open("rezNK_el.txt");

if (fout.fail()){cout<<"error open rezNK.txt\n";return(1);}

cout<<"k--> "; //кол-во эл-ов в подмножестве

cin>>k;

i=0;

fout<<"Данное множество: "<<endl;

while (fin>>a[i])

{fout<<setw(6)<<a[i];

i++;

if ((i%10)==0)fout<<endl;

}

fout<<endl;

fout<<k<<"- элементные подмножества простых чисел: "<<endl;

n=i; //cчитано n элементов: 0-ой, 1-й,..., (n-1)-ый

//выделение подмножеств, b – битовая строка (маска)

b=(1<<k)-1; //в маске k единиц 000...011...1 (1-ое подмножество)

nn=1<<n; //здесь единица n-го разряда

{print (fout, a, n, b); //обработка 1-го подмножества

//получение следующей маски из n единиц

unsigned int m;

m=1;

while ((b&m)==0) // пропуск крайних нулей

{ m=m<<1;}

int bb=0; //счетчик единиц

while ((b&m)!=0) //пока не нуль, обработка единиц

{ bb++; //подсчёт единиц

b=b^m; //обнуление единиц

m=m<<1;

}

b=b|m; // первый 0 после единиц заменяем на 1

//установка bb-1 единиц в конец маски

b=b | ((1<<(bb-1))-1); //новая маска

}

while (b<nn);

fin.close(); fout.close();

return 0;

}

// запись в файл подмножеств из k простых элементов

void print (ofstream &fout, int a[ ], int n, unsigned int b)

{unsigned int m; int i, t;

int B[L];

bool p=true;

i=0; m=1; t=0;

for (i=0; i<n && p; i++)

{if (b&m) //не нуль

{B[t]=a[i]; t++;

if (!prost(a[i])){p=false;}

}

m<<=1;

}

{for (i=0;i<t;i++)

fout<<setw(6)<<B[i];

fout<<endl;

}

}

// проверка числа на простоту

bool prost (int a)

{int d,q;

bool p;

a=abs(a);

p=(a==2) || (a%2!=0);

{d=3; q=int(sqrt (double(a)));

while (d<=q && a%d!=0)

d=d+2; //d+=2;

p=d>q;

}

return p;

}

danN_el.txt

rezNK_el.txt

Данное множество:

5- элементные подмножества простых чисел:

Данное множество:

8- элементные подмножества простых чисел:

Замечание. Сформировать новую битовую строку из k единиц можно с помощью следующих операторов:

s=b & (– int(b));

r=s + b;

b=r | (((b^r)>>2) / s);

где b- предыдущая битовая строка, s,r –переменные.

unsigned int x, s,r;

Используя алгоритм “Решето атосфена” записать в файл все простые числа, не превышающие заданного N.

Дата добавления: 2014-01-06