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

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

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

КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ

Индивидуальное домашнее задание

по дискретной математике.

Студент

Бокарев М.А.

^подпись, дата

^фамилия, инициалы

Группа

АС-11

Принял

Гаев Л. В.

^ученая степень, звание

^подпись, дата

^фамилия, инициалы

Липецк 2012

Метод математической индукции.

1, 2, 3, 4, 5, ...

S_k=

Доказательство:

Методматематичской инукции состоит из трех этапов:

1. Доказать базу индукции, то есть справедливость соотношения для начального случая.

k=1, S₁= =1.

2. Предположить, что соотношение справедливо для всех значений k≤n

3. На основе предположения доказать справедливость для k=n+1

S_n+1=1+2+3+…+n+(n+1)=S_n+(n+1)= +n+1=(n+1)( +1)=(n+1)( )= (n+1)

• Доказать справедливость суммы n элементов арифметической прогрессии.

a_n = a₁+(n-1)d

S_k= ((a₁+ a_k)/2) k

1. S_k = ((a₁+a₁+(1-1)d)/2)1=a₁

2. k ≤ n

3. k=n+1

1. S_k+1= ((2a₁+ (n-1)d)/2)n+a₁+nd=(2a₁(n+1)+n²d+nd)/2=(2a₁(n+1)+(n+1) n d)/2=

= (2a₁+nd)/2*(n+1)

2. S_n+1=S_n+a_n+1=((a₁+a_n)n)/2+a_n+1=((a₁+a_n)n)/2+ a_n + d=((a₁+a_n+1-d)n)/2+a_n+1=

= ((a₁+a_n+1-d) n+2a_n+1)/2= (a₁n + (n+2) a_n+1-dn)/2 = (a₁n+a₁-nd + (n+1)a_n+1-dn)/2=

= (a₁(n+1) + (n+1) a_n+1)/2=((a₁+a_n+1)(n+1))/2

• Доказать.

F_(n)=

1. n=1, F₍₁₎=1

n=2, F₍₂₎=5

n=3, F₍₃₎=14

2. n=k — верно

3. n=k+1

(k+1)(k+1+0.5)(k+1+1)=k(k+1)(k+0.5+1)+2(k+1)(k+1.5)=k(k+1)(k+0.5)+k(k+1)+2(k+1)(k+1.5)=

=k(k+1)(k+0.5)+(k+1)(3k+3)=k(k+1)(k+0.5)+3(k+1)² ⁞3

• Доказать.

C_n=1³+2³+3³+…+n³

C₁=1=1²=

C₂=9=3²=(1+2)²= ²

C₃=36=6²=(1+2+3)²

C_n= ²

1. n=1, C₁=1

2. n=k, C_k= ²

3. n=k+1, C_k+1=C_k+(k+1)³

1³+2³+3³+…+(k+1)³= ³=1³+ ³=1³+((1+1)³+…+(k+1)³)=1³+ +1)³=

=1³+ (n³+3n²+3n+1)=1³+ ³+3 ²+3 + k=

1+C_k+3 + 3 +k

3 ²=(k+1)³-1-3 – k

• Для положительного целого n опредилим aⁿ.

aⁿ : a¹=a, a^k+1=a^ka

Доказать, что a) a^{m + n}=a^m aⁿ , b) (ab)^k=a^kb^k

1. a^m=a*a*a*a*a*a*a*a*a*a*a*…*a

│←———————————→│

m

aⁿ=a*a*a*a*a*a*a*a*a*a*a*…*a

│←———————————→│

n

1. n=1 a^m+1=a^ma=a^ma¹

2. n=k a^m+k=a^ma^k

3. n=k+1 a^(m+k)+1=a^m+ka=a^ma^ka=a^ma^k+1

2. 1) k=1, (ab)¹=ab=a¹b¹

2) k=n, (ab)n

3) k=n+1, (ab)ⁿ⁺¹=(ab)ⁿab=aⁿbⁿab=aⁿabⁿb=aⁿ⁺¹bⁿ⁺¹

• Доказать коректность работы программ для исполнителя «робот».

На поле имеется горизонтальная стена «робот» находится в некоторой клетке ниже стены.

1. Доказать что по данному алгоритму «робот» дойдет до стены.

алг. «до стены»

если сверху свободно

то вверх

«до стены»

все

конец

Индукция идет по количеству клеток до стены.

1. Если индукция =0, то условие ложно и «робот» остается на месте. Программа работает верно.

2. Пусть в ситуации когда «робот» находится на расстоянии k клеток до стены условия верны.

3. Пусть «робот» находится на расстоянии k+1 клеток до стены.

Условие «сверху свободно» истинно. «Робот» сдвигается на расстояние k клеток до стены. Здесь он находится в условиях предположения индукции и выполняет команду «до стены».

Таким образом при k+1 команда выполняется вернро.

1)		n=0	2)		n=k	3)		n=k n=k+1

2. Условия те же.

Требуется закрасить столбец клеток от начального положения до стены и возвратить робота в исходное положение.

алг. «столбец»

если сверху стена

то закрась

иначе

вверх «столбец»

вниз закрась

все

конец

1)		n=0	2)		n=k	3)		n=k n=k+1

3. Горизонтальная стена с проемом.

«Робот» находится в клетке примыкающей к стене снизу.

Требуется переместить «робота» в клетку граничащую с первоначальной, но примыкающую к стене сверху.

алг. «обход»

если сверху свободно

то вверх

иначе

влево «обход»

вправо

все

конец

1)

2)

3)

k=0 k=n k=n k=n+1

k — расстояние до проема

4. На поле имеется горизонтальная стена «робот» находится в некоторой клетке ниже стены.

Требуется переместить «робота» в клетку находящуюся на расстоянии от стены в 2 раза больше первоначального.

алг. «дважды»

если сверху свободно

то вверх

«дважды»

вниз

вниз

все

конец

1)			2)			3)
		n=1
		n=2			n=k			n=k
								n=k+1
					n=2k			n=2k
								n=2(k+1)

• Задание не помню.

n≥8

n=3k+5m

1. n=8, k=1, m=1

n=3+5

2. n=t

t=3k+5m

3. n=t+1

t+1=3k_t+1+5m_t+1

t+1=3k_t+5m_t+1

1. если m_t>0, то 3k_t+5(m_t-1+1)+1=t+1, t+1=3k_t+5m_t-5+6

t+1=3(k_t+2)+5(m_t-1)

k_t+1=k_t+2

m_t+1=m_t-1

2. m_t=0

t+1=3k_t+1+1

k≥3

t+1=3(k_t-3+3)+1

t+1=3(k_t-3)+10

k_t+1=k_t-3

m_t+1=2

• Задание не помню.

n≥6, n!>n³

1. при n=6 6!>216

720>216

2. при n=k верно k!>k³

3. n=k+1 (k+1)!˅(k+1)³

(k+1)!=k!(k+1)=k!k+k!

(k+1)³=k³+3k²+3k+1

k!(k+1)˅k³+3k²+3k+1

k!˅(k³+3k²+3k+1)/(k+1)

k!>(k+1)²

так как k! по второму пункту >k³, то нужно доказать что k³>(k+1)²

• function opd;

var x; real;

begin

read (x);

if not eof them;

opd;

write (x);

end;

Реализация на Си:

#include <stdio.h>

#include <string.h>

#include <conio.h>

void main (void)

{

char stroka[20];

FILE *fp;

fp=fopen("ФАЙЛ","r");//ФАЙЛ - открываемый файл

if(NULL==fgets(stroka,20,fp))

printf("Не удалось прочитать строку");

else

strrev(stroka);

printf("%s",stroka);

fclose(fp);

getch();

}

• На выходе будет число входного файла в обратном порядке.