Лабораторная работа №4 по дисциплине «Информатика» Арифметические задачи Группа: авт-010



Скачать 33.58 Kb.
Дата30.11.2012
Размер33.58 Kb.
ТипЛабораторная работа


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСТИЕТ


Лабораторная работа №4

по дисциплине «Информатика»

Арифметические задачи

Группа: АВТ-010
Студенты: Антонов Н.А., Довиденко Р.Е.
Преподаватель: Романов Е.Л.


НОВОСИБИРСК 2010

Задание


Число называется совершенным, если оно равно сумме всех своих делителей, например, 6=1+2+3, 28=1+2+4+7+14. Найти все совершенные числа в заданном интервале.

Теоретические сведения


Совершенным называется число, равное сумме всех своих делителей (включая 1, но исключая само число). Наименьшее из совершенных чисел 6 равно сумме трех своих делителей 1, 2 и 3. Следующее совершенное число 28=1+2+4+7+14. Ранние комментаторы Ветхого завета, пишет в своей книге «Математические новеллы» Мартин Гарднер, усматривали в совершенстве чисел 6 и 28 особый смысл. Разве не за 6 дней был сотворен мир, восклицали они, и разве Луна обновляется не за 28 суток? Первым крупным достижением теории совершенных чисел была теорема Евклида о том, что число 2n-1*(2n-1) - четное и совершенное, если число 2n-1 - простое. Лишь две тысячи лет спустя Эйлер доказал, что формула Евклида содержит все четные совершенные числа. Поскольку не известно ни одного нечетного совершенного числа (у читателей есть шанс найти его и прославить свое имя), то обычно, говоря о совершенных числах, имеют в виду четное совершенное число.

Проектирование программы

Обсуждение основных идей алгоритма


Идея: Для нахождения данных чисел можно использовать перебор всех чисел, что займёт большое количество времени, но, зная формулу 2к*(2к+1-1), можно сократить время их нахождения. Во втором случае при изменении k получается множество чисел, которые проверяются на «совершенство»

«Составные части» программы


  • Инициализация таймера

long t=clock();


  • Цикл перебора чисел для нахождения совершенного.

for (s=0,i=1;i
{if (j%i==0) s+=i;}



  • Формула вычисления числа для отбора на совершенное.

v=1<
j=v*(2*v-1);


  • Условие определения совершенного числа (сохраняется в массиве).


if (s==j) C[p++]=j


  • Вывод совершенного числа, степени двойки (на данный момент работы программы) и времени работы (в миллисекундах)

cout << j << endl;

cout << "k=" << k << " t=" << clock()-t << endl;
Переменные:

i - счётчик делителей

v – 2к

C[100] – массив совершенных чисел

k – счётчик степеней двойки

j – счётчик делимых

p – счётчик совершенных чисел

s – сумма делителей

Текст программы с комментариями


using namespace std;

void main(){

_int64 i,v,C[100],k,j,p,s;

v=200000000;

k=0;

p=0;

for (k=1; k<30; k++){ // запуск основного цикла программы, увеличивающего степень двойки

long t=clock(); // запоминание текущего времени для таймера

v=1<
j=v*(2*v-1); // применяем формулу

for (s=0,i=1;i
{

if (j%i==0) s+=i; // Если счётчик является делителем числа, то он складывается с

// другими делителями

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

}

for (i=0;i
// цикл для вывода массива

cout << C[i] << endl; // вывод массива

}

Пример работы программы


6

k=1 t=0

28

k=2 t=0

k=3 t=0

496

k=4 t=0

k=5 t=0

8128

k=6 t=0

k=7 t=0

k=8 t=0

k=9 t=0

k=10 t=31

k=11 t=78

33550336

k=12 t=344

k=13 t=1312

k=14 t=5219

k=15 t=20845

Ошибки и неточности

Выводы


Способ перебора всех чисел не дает эффективного результата (времени тратится значительно больше нежели в отборе по формуле). Для решения данной задачи предпочтительнее использование формулы. Но даже при использовании формулы на 16, 17 степенях двойки подсчёты занимают уже десятки секунд.


.


Похожие:

Лабораторная работа №4 по дисциплине «Информатика» Арифметические задачи Группа: авт-010 iconЛабораторная работа №25 по дисциплине "Информатика" т ема : субд access. Создание многотабличной базы данных. Задание
Группа – содержит информацию о студентах
Лабораторная работа №4 по дисциплине «Информатика» Арифметические задачи Группа: авт-010 iconПрактикум по дисциплине «информатика» для студентов направлений 230100. 62 «Информатика и вычислительная техника»
Лабораторная работа Команды работы с дисками, файлами и каталогами ос ms dos 9
Лабораторная работа №4 по дисциплине «Информатика» Арифметические задачи Группа: авт-010 iconЛабораторная работа № Арифметические выражения
Арифметические выражения строятся из операндов, арифметических операций и круглых скобок
Лабораторная работа №4 по дисциплине «Информатика» Арифметические задачи Группа: авт-010 iconКурсовая работа по дисциплине информатика студента Чиж А. В шифр 9403030028 группа 230105

Лабораторная работа №4 по дисциплине «Информатика» Арифметические задачи Группа: авт-010 iconМетодические указания к лабораторным работам по дисциплине "Информатика" для студентов специальности 230102
Лабораторная работа №1 "Интегрированная среда программирования Borland C++. Простые программы "
Лабораторная работа №4 по дисциплине «Информатика» Арифметические задачи Группа: авт-010 iconЛабораторная работа №1 по дисциплине "Системы искусственного интелекта"
Исчисление предикатов первого порядка является теоретической основной множества формализмов методов искусственного интеллекта. Задачи...
Лабораторная работа №4 по дисциплине «Информатика» Арифметические задачи Группа: авт-010 iconЛабораторная работа №2 по дисциплине "Системы искусственного интеллекта"
Дедуктивные и индуктивные рассуждения. Задачи на поиск доказательства методом резолюций
Лабораторная работа №4 по дисциплине «Информатика» Арифметические задачи Группа: авт-010 iconЛабораторная работа №1 по дисциплине сии факультет: пми группа: пм 73 Студенты: Безбородов Б. Е. Преподаватели
Изучение основных стратегий решения задач. Приобретение навыков выбора адекватных стратегий в зависимости от типа задачи. Выбор инструмента...
Лабораторная работа №4 по дисциплине «Информатика» Арифметические задачи Группа: авт-010 iconЛабораторная работа №1 по дисциплине «Сети ЭВМ и средства телекоммуникации» Утилиты tcp/ip алексашенков Д. В. Группа с-65
Цель работы: практически освоить работу с утилитами tcp/IP, необходимыми в следующих работах
Лабораторная работа №4 по дисциплине «Информатика» Арифметические задачи Группа: авт-010 iconЛабораторная работа №1 Работа в Oracle Database Express Edition 1 Лабораторная работа №6
Лабораторная работа Выполнение расчетов с использованием программирования в среде Visual Basic for Applications
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org