2015-06-10
375
{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-го разряда
do
{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;
}
If (p)
{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);
If (p)
{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
123 13 5 7 43 17
29 11 33 41
RezNK_el.txt
Данное множество:
123 13 5 7 43 17 29 11 33 41
5- элементные подмножества простых чисел:
13 5 7 43 17
13 5 7 43 29
13 5 7 17 29
13 5 43 17 29
13 7 43 17 29
5 7 43 17 29
13 5 7 43 11
13 5 7 17 11
13 5 43 17 11
13 7 43 17 11
5 7 43 17 11
13 5 7 29 11
13 5 43 29 11
13 7 43 29 11
5 7 43 29 11
13 5 17 29 11
13 7 17 29 11
5 7 17 29 11
13 43 17 29 11
5 43 17 29 11
7 43 17 29 11
13 5 7 43 41
13 5 7 17 41
13 5 43 17 41
13 7 43 17 41
5 7 43 17 41
13 5 7 29 41
13 5 43 29 41
13 7 43 29 41
5 7 43 29 41
13 5 17 29 41
13 7 17 29 41
5 7 17 29 41
13 43 17 29 41
5 43 17 29 41
7 43 17 29 41
13 5 7 11 41
13 5 43 11 41
13 7 43 11 41
5 7 43 11 41
13 5 17 11 41
13 7 17 11 41
5 7 17 11 41
13 43 17 11 41
5 43 17 11 41
7 43 17 11 41
13 5 29 11 41
13 7 29 11 41
5 7 29 11 41
13 43 29 11 41
5 43 29 11 41
7 43 29 11 41
13 17 29 11 41
5 17 29 11 41
7 17 29 11 41
43 17 29 11 41
Данное множество:
123 13 5 7 43 17 29 11 33 41
8- элементные подмножества простых чисел:
13 5 7 43 17 29 11 41
Замечание. Сформировать новую битовую строку из k единиц можно с помощью следующих операторов:
|
|
|
s=b & (– int(b));
r=s + b;
b=r | (((b^r)>>2) / s);
Где b- предыдущая битовая строка, s,r –переменные.
unsigned int x, s,r;
Пример 2. Решето Эратосфена.
Используя алгоритм “Решето атосфена” записать в файл все простые числа, не превышающие заданного N.
Решето представляет битовую строку для чисел от 0 до N. Сами числа не хранятся. Во все биты строки (кроме 0-го и 1-го,где -0) записываются 1. Выбирается самое маленькое число, из решета удаляются все кратные ему числа (их биты обнуляются), само число помещается в файл.Таким образом из решета удаляются все числа, не являющиеся простыми, остаются единичными только биты, соответствующие простым числам, а сами числа собираются в файле.
