Задача 5. Учимся подсчитывать эффективность программы 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Задача 5. Учимся подсчитывать эффективность программы



Для этого давайте научимся подсчитывать время выполнения программы. Решим задачу нахождения простых чисел в диапазоне от 1 до 1000000. Напишем метод проверки, является ли число простым, и используем его для подсчета количества чисел. В начале цикла сохраним текущее время, по выходу из цикла вычтем текущее время из сохраненного и выведем результат на экран.

 

Текст программы:

using System;   namespace Prostye { class Program { static bool IsSimple(int n) { for (int i = 2; i <= n / 2; i++) if (n % i == 0) return false; return true; }   static void Main(string[] args) { DateTime start = DateTime.Now; int k=0; for (int i = 2; i < 1000000; i++) if (IsSimple(i)) { k++; Console.WriteLine("{0} {1}",k,i); } Console.WriteLine(k); Console.WriteLine(DateTime.Now - start); } } }

 

На самом деле в методе определения простоты числа можно заменить условие на i<=Math.Sqrt(n). Создайте новый метод с новым условием. Подсчитайте время выполнения программы с использованием двух различных методов.


 

Задача 6. Дано натуральное число n. Вычислить n!

Без использования рекурсии:

static uint Factorial(uint n) { uint res = 1; for (uint i = 0; i <= n; i++) res *= i;//res=res*i return res; }

 

С использованием рекурсии. (0!=1, n!=n*(n-1)!):

static uint Factorial(uint n) { if (n == 0) return 1; else return Factorial(n - 1) * n; }

 

Задача 7. Последовательность Фибоначчи

Последовательность Фибоначчи определяется так: a0=0, a1=1, ak=ak-1+ak-2 при k>=2. Дано n, вычислить an

Вариант 1. Использования цикла for:

static uint Fib(int n) { uint a0 = 0; uint a1 = 1; uint a=a1; for(int i=2;i<= n;i++) { a = a0 + a1; a0 = a1; a1 = a; } return a1; }

 

Вариант 2. Использование рекурсии:

static uint Fib(uint n) { if (n == 0) return 0; if (n == 1) return 1; return Fib(n - 1) + Fib(n - 2); }

Задача 8. “Ханойская башня”

Реализовать на C# рекурсивный алгоритм игры «Ханойская башня»:

using System;   namespace Hanoi { class Program {   static void Move(int n,int a,int b,int c) { if (n > 0) { Move(n - 1, a, c, b); Console.WriteLine("{0} => {1}", a, b); Move(n - 1, c, b, a); } }   static void Main(string[] args) { Move(4, 1, 2, 3); } } }

 

Рекурсия способствует лучшему пониманию некоторых проблем, например, для головоломки «Ханойская башня» она дает простое и изящное решение. К сожалению, у рекурсии есть и свои недостатки: иногда ее использование очевидно, но неэффективно.

Так, рекурсивный алгоритм генерирования чисел Фибоначчи требует от программы многократного расчета одних и тех же величин. Это замедляет работу настолько, что расчет более 50 значений становится непрактичным. Таким образом, при разработке рекурсивного метода следует задуматься об его эффективности

Домашнее задание

1. Написать метод возвращающий минимальное из трех чисел;

2. Написать метод подсчета количества цифр числа;

3. С клавиатуры вводятся числа, пока не будет введен 0. Подсчитать сумму всех нечетных положительных чисел;

4. Реализовать метод проверки логина и пароля. На вход подается логин и пароль. На выходе истина, если прошел авторизацию, и ложь, если не прошел. Используя метод проверки логина и пароля, написать программу: пользователь вводит логин и пароль, программа пропускает его дальше или не пропускает. С помощью цикла do while ограничить ввод пароля тремя попытками;

5. а) Написать программу, которая запрашивает массу и рост человека, вычисляет его индекс массы и сообщает, нужно ли человеку похудеть, набрать вес или все в норме;
б) *Рассчитать, на сколько кг похудеть или сколько кг набрать для нормализации веса.

6. *Написать программу подсчета количества “Хороших” чисел в диапазоне от 1 до 1 000 000. Хорошим называется число, которое делится на сумму своих цифр. Реализовать подсчет времени выполнения программы, используя структуру DateTime.

7. a) Разработать рекурсивный метод, который выводит на экран числа от a до b;
б) *Разработать рекурсивный метод, который считает сумму чисел от a до b.

Достаточно решить 3 задачи. Разбивайте программы на подпрограммы. Переписывайте в начало программы условие и свою фамилию. Все программы делайте в одном решении.

Дополнительные материалы

1. Демоверсии ГИА по информатике;

2. Индекс массы тела на Википедии.

3. Алгоритмы. Теория и практическое применение. Род Стивенс. Глава “Рекурсии”.

4. “Ханойская башня” на Википедия.

Используемая литература

Для подготовки данного методического пособия были использованы следующие ресурсы:

1. Т.А. Павловская. “Программирование на языке высокого уровня”, 2009 г.;

2. Г. Шилдт. “C# 4.0. Полное руководство”;

3. Алгоритмы. Теория и практическое применение. Род Стивенс, Москва 2016 г.

4. MSDN.



Поделиться:


Последнее изменение этой страницы: 2016-12-29; просмотров: 690; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 52.205.159.48 (0.087 с.)