Курсовая работа: Синтаксический анализатор полиномов
Алгоритм решения этой задачи включает три этапа:
1. поиск простых чисел, не превышающих заданного N;
2. преобразование десятичного вида простых чисел в бинарный вид;
3. поиск максимального числа единиц в бинарном представлении простых чисел.
Поиск простых чисел, не превышающих заданного N основан на алгоритме, называемом "Решето Эратосфена" [6]. Этот алгоритм заключается в следующем: берем число 2 и выбрасываем все числа кратные 2. Из оставшихся чисел оставляем наименьшее (в данном случае это число 3) и выбрасываем все числа кратные 3, и так далее. Если первое оставшееся число превышает , то работу прекращаем, поскольку все отобранные и оставшиеся числа являются простыми.
Преобразование десятичного вида простых чисел в бинарный вид реализован по следующей схеме. Для каждого простого числа берется строка длиной в 33 символа (размер переменной типа int, равный 4 байтам, умноженный на количество бит в одном байте, т. е. 8, и плюс один символ для "\0"). В нее заносятся нули или единицы. Затем для каждого простого числа выполняется поразрядный сдвиг вправо на количество бит от 31 до 0 с операцией поразрядное "и" (операция наложения маски вида 0x1). Сдвиг целого числа вправо на n разрядов эквивалентен целочисленному делению его на 2n . Результат этих операций сравнивается с 1 и в зависимости от истинности или ложности этого выражения увеличиваем счетчик единиц и заносим в строку 1 или увеличиваем счетчик нулей и заносим в строку 0 соответственно.
Имея для каждого простого числа количество единиц в его бинарном представлении, находим число или числа с максимальным количеством единиц.
Ниже приведен код программы нахождения простых чисел, не превосходящих заданного N, с максимальным количеством единиц в бинарном представлении.
#include "stdafx.h"
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int i, j, x;// счетчики
int *a, *b;
//ввод n
int n;
cout<<"Input n: "; cin>>n;
a = new int [n]; //массив натуральных чисел
b = new int [n]; //массив простых чисел
//массив натуральных чисел
for (i=1; i<=n; i++)
a[i]=i;
//поиск простых чисел
for (i=2; i<=sqrt((float )n); i++)
{