Курсовая работа: Синтаксический анализатор полиномов

Алгоритм решения этой задачи включает три этапа:

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++)

{

К-во Просмотров: 224
Бесплатно скачать Курсовая работа: Синтаксический анализатор полиномов