Исследовательская работа Комбинаторика: вчера, сегодня, завтра. Автор: Кравченко Вадим Алексеевич 7 «К» класс



Скачать 167.31 Kb.
Дата23.12.2012
Размер167.31 Kb.
ТипИсследовательская работа


Фонд развития Международного университета

НОУ средняя общеобразовательная школа «Росинка»

Исследовательская работа

Комбинаторика: вчера, сегодня, завтра.

Автор: Кравченко Вадим

Алексеевич

7 «К» класс

Научный руководитель:

Войнова Татьяна Олеговна,

учитель математики НОУ СОШ

«Росинка»

Москва

2008

Оглавление

Введение 3

Глава 1. Три правила комбинаторики и класс задач, решаемый с использованием этих правил

1.1 Правило суммы 5 1.2 Правило произведения 6 1.3 Правило для вычисления числа перестановок элементов внутри

множества 10 Глава 2. Создание алгоритмов и написание программ, реализующих

решение комбинаторных задач из выбранного класса. Создание математического тренажера.

2.1 Организация и методы создания математического тренажера 13

2.2 Алгоритмы решения задач на выбранные правила 14

2.2.1. Алгоритм решения задачи на комбинаторное правило

произведения 14

2.2.2 Алгоритм решения задач на вычисление числа перестановок. 16

2.3. Модель созданного математического тренажера. 20

Заключение. 21

Приложение. Модель математического тренажера. 22

Список источников информации. 25

Введение

Число, положение и комбинация –

три взаимно пересекающиеся, но

различные сферы мысли, к которым

можно отнести все математические

идеи".

Дж. Сильвестр (1844 г.)

Человеку часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия. Разные пути или варианты, которые приходится выбирать человеку, складываются в самые разнообразные комбинации. И целый раздел математики, называемый комбинаторикой, занят поиском ответов на вопросы: сколько всего есть комбинаций в том или другом случае.

С комбинаторными величинами приходится иметь дело представителям многих специальностей: экономисту, ученому–химику, биологу, лингвисту конструктору, диспетчеру, специалисту в области защиты информации и т.п. Усиление интереса к комбинаторике в последнее время обуславливается бурным развитием кибернетики и вычислительной техники.

Однако теоретических да и практических знаний по комбинаторике, которые давали бы возможность решать хотя бы несложные задачи по дан­ному разделу математики, у учащихся 7-8 классов явно недостаточно.
По­этому в своей работе я бы хотел познакомить моих ровесников с некоторыми простейшими комбинаторными формулами, показать, как решаются задачи с их использованием, и продемонстрировать возможность создания тренажера с использованием средств ИКТ.

Ребята смогут использовать полученные знания в дальнейших исследованиях по биологии, химии и т.д., а также блеснуть эрудицией на математических КВНах и олимпиадах. Свою работу я начал со знакомства с основными понятиями и формулами комбинаторики, а также с истории ее возникновения и развития. Здесь мне пришлось изучить и проанализировать достаточно большое количество литературы по выбранной тематике. Оказалось, что знание всего лишь трех несложных правил подсчета числа возможных комбинаций (правила суммы, произведения и правила для подсчета числа возможных перестановок элементов) уже позволяет нам решать очень обширный и интересный класс задач, о чем пойдет разговор в первой главе моей работы.

Я отобрал задачи, которые, на мой взгляд, были наиболее интересны, их формулировки звучали занимательно, а их решение осуществлялось по указанным выше трем правилам. Некоторые из них я не просто решил, а соз­дал с помощью своего научного консультанта алгоритмы решения их на компьютере с использованием языка Visual Basic, чтобы затем использовать полученные программы в тренажере. Речь о том, какие задачи были выбраны для программирования и как происходил процесс написания непосредст­венно алгоритмов, идет во второй главе моей работы. В приложении продемонстрирована модель математического тренажера. Хочется надеяться, что выполненная мною работа будет полезной не только для меня, ибо я прекрасно усовершенствовал свои знания и по комбинаторике, и по информатике, но и для многих учеников 7-8 классов, желающих узнать больше о комбинаторике и укрепить свои навыки в программировании.

Глава 1. Три правила комбинаторики и класс задач, решаемый с использо­ванием этих правил

КОМБИНАТОРИКА – раздел математики, в котором изучаются различные вопросы, связанные с взаимным расположением частей данного множества, состоящего обычно из конечного числа элементов. Комбинаторные задачи обладают общей особой приметой. Этой приметой является вопрос задачи, который всегда можно сформулировать так, что он будет начинаться словами: «Сколькими способами …?». Комбинаторные задачи различаются по подходам к решению. Рассмотрим некоторые основные комбинаторные идеи, лежащие в основе решения некоторых из них.

    1. Правило суммы

Рассмотрим следующий пример: если на одной полке книжного шкафа стоит 30 различных книг, а на другой - 40 различных книг (и не таких, как на первой полке), то выбрать одну книгу, из стоящих на этих полках можно 30+40=70 способами. Обобщением этого примера является правило суммы. Правило суммы: если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор "либо А, либо В" можно сделать (m+n) способами.

При использовании правила суммы в такой формулировке нужно следить, чтобы ни один из способов выбора объекта А не совпадал с каким-нибудь способом выбора объекта В. Приведем еще один пример задачи, решаемый с помощью вышеуказанного правила. При формировании кабинета министров имеется 10 претендентов на пост министра здравоохранения, 20 – на пост министра энергетики, 25 – на пост министра образования. Ни один из претендентов не претендует одновременно на два поста. Сколькими способами можно выбрать одного человека или на пост министра здравоохранения, или на пост министра образования, или на пост министра энергетики?

Решение. 10+20+25=55 способов.

1.2. Правило произведения.

Рассмотрим такой пример. В магазине «Ткани» имеются ткани четырех расцветок и шесть видов отделки к ним. Сколькими способами можно купить ткань и отделку для платья?

Решение. Сначала выберем ткань, это можно сделать четырьмя способами. В комплект к ней (к каждому из четырех способов) можно подобрать шестью способами отделку, т. е. можно подобрать четыре раза по шесть комплектов: 4•6 = 24. Всего существует 24 способа. При решении такого вида задач применяется правило произведения. Правило произведения.

Если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А, В) в указанном порядке может быть выбрана mn способами.

Обобщение правила произведения на большее, чем 2, количество множеств, можно сделать так.

Пусть нам даны k множеств по n1, n2, n3,, n4,... ,nk элементов каждое, и нам нужно произвести выбор по одному в каждом из множеств, тогда число возможных способов находим следующим образом:

N = n1 n2 n3 n4 ...nk.

Вот еще несколько задач, решаемых с помощью правила произведения и его обобщения.

  1. В магазине «Сувениры» имеются подсвечники шести видов и три вида вазочек к ним. Сколькими способами можно составить подарочный комплект из подсвечника и вазочки?

Решение. Вазочку можно выбрать шестью способами и к каждой вазочке тремя способами можно подобрать подсвечник: 6•3 = 18 способов.

  1. Слог называется открытым, если он начинается с согласной буквы, а заканчивается гласной. Сколько открытых двухбуквенных слогов можно написать, используя буквы «а», «б», «в», «г», «е», «и», «о»? Выпишите эти слоги.

Решение: 4(количество гласных) * 3(количество согласных) = 12. Все слоги легко выписать, если заполнить таблицу




А

Е

И

О

Б

Ба

Бе

Би

Бо

В

Ва

Ве

Ви

Во

Г

Га

Ге

Ги

Го



  1. В магазине «Все для чая» имеются в продаже шесть видов разных чашек, пять видов блюдец и три вида ложек. Сколькими способами можно составить набор из трех предметов?

Решение. Чашку можно выбрать шестью способами, к каждой из шести чашек можно подобрать пятью способами блюдце, к каждому из 30 комплектов чашки с блюдцем можно подобрать тремя способами ложку:

6•5•3 = 90 способов.

4. От Гулливера в страну Лилипутов ведут три секретные дороги, а в страну Великанов – четыре. Сколькими способами Гулливеру можно попасть в страну Великанов?

Решение. 3•4 = 12 способов .

  1. В магазине «Канцелярские товары» имеются в продаже шесть видов цветных карандашей, семь видов красок и пять видов цветной бумаги. Сколькими способами можно составить комплект для уроков художественного труда, состоящий из коробки цветных карандашей, красок и набора цветной бумаги?

Решение: 6•7•5 = 210 способов.

  1. . Сколько пятизначных чисел можно составить, используя только цифры 3 и 5?.

Решение. Первую цифру можно выбрать двумя способами, вторую – также двумя способами, третью – двумя и так далее. Получаем:

N = 2•2•2•2•2 = 25.

В данной задаче порядок расположения объектов не имеет значения.

  1. .Монету бросают трижды. Сколько различных последовательностей «орлов» и «решек» при этом можно получить?

Решение: 23 = 8 различных последовательностей.

  1. . Рекламный агент составляет эскиз рекламного щита. Он решил сделать фон в виде квадратной таблицы 2•2, каждую клетку которой закрасить либо в зеленый, либо в желтый цвет. Сколькими способами это можно сделать?

Решение. 24 = 16 различных способов.

  1. . На сколько увеличится число способов в предыдущей задаче, если сделать таблицу 3•3?

Решение: 29 = 512 способов выкрасить таблицу 3•3. Число способов увеличится на 512 – 16 = 496.

  1. . Алфавит племени Мумбо-Юмбо состоит из букв А, У и С. Словом является любая последовательность, состоящая из 4 букв. Сколько слов в языке племени Мумбо-Юмбо?

Решение: 34 = 81 слово.

  1. . С течением времени наука в племени Мумбо-Юмбо резко шагнула вперед и словарный запас увеличился. Словом стала считаться любая последовательность, состоящая не более чем из 4 букв. Сколько слов стало в словаре племени Мумбо-Юмбо?

Решение. Получаем в языке племени Мумбо-Юмбо слова, состоящие из одной, двух, трех и четырех букв. Подсчитаем их количество отдельно:

однобуквенных слов – 3;
слов из двух букв – 32 = 9;
слов из трех букв – 33 = 27;
слов из четырех букв – 81.

Всего 3 + 9 + 27 + 81 = 120 слов.

  1. «Опять восьмерка!» – горестно воскликнул председатель клуба велосипедистов, взглянув на погнутое колесо своего велосипеда, и продолжим: «А все потому, что при вступлении в клуб мне выдали билет за номером 008. И теперь не проходит и месяца, чтобы то на одном, то на другом колесе не появилась восьмерка. Надо поменять номер билета». Чтобы председателя не обвинили в суеверии, он решил объявить полную перерегистрацию всех членов клуба и выдавать только билеты с номерами, не содержащими цифру 8. Сколько членов было в клубе, если известно, что использованы все трехзначные номера, не содержащие ни одной восьмерки?

Решение: 93 = 729 членов в клубе велосипедистов.

  1. В другом клубе велосипедисты были еще суевернее. И так как число 0 похоже на вытянутое колесо, решили отказаться и от него и обходиться только восемью цифрами. Сколько членов было в этом клубе, если номера билетов были также трехзначными?

Решение: 83 = 512 членов в клубе велосипедистов.

  1. . Назовем «симпатичным» число, если в его записи участвуют только нечетные цифры. Сколько существует четырехзначных «симпатичных» чисел?

Решение: 54 = 625 четырехзначных «симпатичных» чисел.

    1. 1.3. Правило для вычисления числа перестановок элементов внутри множества



В сборнике занимательных задач Я.Перельмана «Живая математика» есть рассказ «Бесплатный обед». В нем описывается случай, происшедший с десятью выпускниками, которые не могут отпраздновать окончание школы, потому что никак не решат: в каком порядке им сесть.

На выручку им пришел официант, который предложил сегодня сесть, как придется, на другой день придти и сесть по-другому и так каждый день, пока не наступит такой день, когда они опять сядут так, как сидят сегодня. И тогда официант обещал угостить всех бесплатным обедом. Как вы думаете, долго ли друзьям придется дожидаться бесплатного обеда?

Решение. Первого, сидящего за столом, можно выбрать десятью способами, второго к нему можно выбрать девятью способами, третьего – восемью и т.д. Таким образом, имеем: Pn = 10•9•8•...•2•1.

В данной задаче необходимо подсчитать число перестановок из 10 элементов.

Перестановкой из п элементов называют упорядоченный набор этих элементов. Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок

Pn = n!,

где n! = 1 * 2 * 3 ... n. Выражение вида п! называется факториалом, читается «Эн факториал».

Заметим, что удобно рассматривать 0!, полагая, по определению, 0! = 1.

Произведение Pn = 10•9•8•...•2•1 можно записать короче Pn = 10! = 3628800. Число n! с ростом n растет очень быстро. Это означает, что на самом деле официант ничем не рисковал, так как обещанное событие произойдет почти через 10 000 лет.

Приведем еще несколько примеров задач, решаемых с помощью формулы для вычисления числа перестановок.

  1. Сколько существует трехзначных чисел, в записи которых цифры 1; 2; 3 встречаются ровно по одному разу?

Решение: Pn = 3! = 6 чисел.

2 . Сколькими способами можно выложить в ряд красный, черный, синий, белый и зеленый шарики?

Решение: Pn = 5! = 120 способов.

3 . Всем известна знаменитая басня Ивана Крылова «Квартет»:

Проказница Мартышка,
Осел, Козел,
Да косолапый Мишка
Затеяли квартет…

Как помнится, герои басни никак не могли усесться. Подсчитайте, сколькими способами герои квартета могут пересаживаться?

Решение. Pn = 4! = 24 способа.

4 . Необходимо составить школьное расписание на один учебный день для шестого класса из шести предметов. Сколькими способами это можно сделать?

Решение. Pn = 6! = 720 способов.

5.Несколько стран в качестве символа своего государства решили использовать флаг в виде четырёх вертикальных полос, одинаковых по ширине, но разных по цвету: белый, синий, красный, зелёный. У каждой страны свой, отличный от других, флаг.

а) Сколько всего стран могут использовать такую символику?

б) Сколько всего стран могут использовать такую символику с верхней белой полосой?

в) Сколько всего стран могут использовать такую символику с нижней зелёной полосой?

Решение: а) 4*3*2*1 =24 страны, б) 6 стран (четвертая часть), в) 6 стран

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

Глава 2. Создание алгоритмов и написание программ, реализующих решение комбинаторных задач из выбранного класса. Создание математического тренажера.

2.1 Организация и методы создания математического тренажера

В паспорте проекта была выдвинута гипотеза, согласно которой у учащихся 7-8 классов не хватает материала для изучения такого важного раздела математики, как комбинаторика. Чтобы принять или опровергнуть эту гипотезу среди учащихся школы «Росинка» было проведено анкетирование. Анкета включала в себя следующие вопросы:

  1. В каком классе Вы учитесь?

  2. Известно ли Вам такое понятие, как «комбинаторика»?

  3. Что такое факториал?

  4. Сколько четырехзначных чисел можно получить из цифр 1, 2, 3 и 4, если ни одна из этих цифр не может повториться дважды?

Результаты анкетирования были занесены в таблицу. В колонке со словом «да» указывалось количество человек правильно ответивших ни вопросы 2-4, а в колонке со словом «нет» - число человек, давших неправильный ответ или не знающие, как ответить вообще на поставленный вопрос.

Число ответивших учащихся

Номер вопроса

2

3

4

да

нет

да

нет

да

нет

7 чел. из 5-6 классов

1

6

1

6

0

7

8 чел. из 7-8 классов

1

7

1

7

0

8

3 чел. из 9-11 классов

1

2

1

2

1

2

Хотя количество опрошенных не позволяет считать данную выборку достаточно репрезентативной, уже можно сделать вывод о том, что даже самые простые понятия комбинаторики большинству учащихся неизвестны.

Чтобы познакомить учащихся с решением некоторых комбинаторных задач с использованием программных средств, было отобрано несколько задач разных видов. Часть из них была решена при помощи программы, написанной на языке VISUAL BASIC, а часть включена в модель математического тренажера.

2.2 Алгоритмы решения задач на выбранные правила

2.2.1. Алгоритм решения задачи на комбинаторное правило произведения.

Задача на это правило была выбрана следующая.

Номер автомобиля состоит из трех букв и четырех цифр. Сколько существует различных автомобильных номер, если три буквы берутся из 29 букв русского алфавита?

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



2.2.2 Алгоритм решения задач на вычисление числа перестановок.

Здесь были отобраны три задачи.

1. Какие трехзначные числа можно записать с помощью цифр 3,7,1 при условии что в записи числа не должно быть одинаковых цифр? Сколько таких чисел?

2. Сколько трехзначных чисел можно составить из цифр 1,2,4,6, если никакую цифру не использовать более одного раза?

3. Всем известна знаменитая басня Ивана Крылова «Квартет»:

Проказница Мартышка,
Осел, Козел
Да косолапый Мишка
Затеяли квартет…

Как помнится, герои басни никак не могли усесться. Подсчитайте, сколькими способами герои квартета могут пересаживаться?

Алгоритмы решения этих задач приведены ниже:







2.3. Модель созданного математического тренажера.
Модель математического тренажера включает в себя выведенные на экран монитора определения комбинаторики, факториала, правил произведения и подсчета числа перестановок, а также нескольких задач, которые предлагаются для самостоятельного решения.

Модель тренажера приведена в приложении.

Работа данной модели математического тренажера была опробована на 5 учащихся. Из них:

решили все 4 предложенные задачи – 0 человек

решили 3 из 4 предложенных задач - 3 человека

решили 2 из 4 предложенных задач - 2 человека
Апробация модели тренажера даже на таком небольшом количестве учащихся уже позволяет сделать вывод о том, что его использование при изучении комбинаторики может быть полезным и существенно повысит уровень знаний по некоторым разделам математики.

Заключение

Изучив всего лишь небольшую часть имеющейся литературы по комбинаторике, я пришел к выводу о том, что усовершенствование навыков решения задач по данному разделу математики существенно помогут мне и моим коллегам-ученикам осваивать теорию вероятностей и математическую статистику, так как именно наука о подсчете числа комбинаций лежит в основе методов решения простейших вероятностных задач.

В дальнейшем мне бы хотелось продолжить работу над этой тематикой, разработать полноценный тренажер, а не только его модель, куда включить задачи и на подсчет числа сочетаний и размещений. Если эта работа удастся, то разработанный тренажер можно будет использовать и на уроках, посвященных теории вероятностей.

Приложение. Модель математического тренажёра.















Список источников информации.


  1. Айгнер М. Комбинаторная теория. М.: Мир, 1982.

  2. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М.: Мир, 1998

  3. Клейн Ф. Лекции о развитии математики в XIX столетии. М.: Наука, 1989

  4. Лютикас В.С. Школьнику о теории вероятностей. М.: Просвещение, 1976.

  5. Рыбников К.А. Введение в комбинаторный анализ. М: МГУ, 1985.

  6. Рыбников К.А. История математики. М.: МГУ, 1994.

  7. Стенли Р. Перечислительная комбинаторика. М.: Мир, 1990.

  8. Халамайзер А. Я. Комбинаторика и бином Ньютона. — М.: Просвещение, 1980.

  9. Халамайзер А. Я. Математика? — Забавно!: Для сред, классов. — М.: Изд-во МПИ, 1989.

  10. Холл. М. Комбинаторика. М.: Мир, 1970.

  11. История математики с древнейших времён до начала XIX столетия / Под ред. А.Н. Колмогорова, А.П. Юшкевича. М: Наука, 1970-1972. T.1-3.






Похожие:

Исследовательская работа Комбинаторика: вчера, сегодня, завтра. Автор: Кравченко Вадим Алексеевич 7 «К» класс iconРостовская область: вчера, сегодня, завтра
Ростовская область: вчера, сегодня, завтра: материалы интернет-конференции Ростовского государственного экономического университета...
Исследовательская работа Комбинаторика: вчера, сегодня, завтра. Автор: Кравченко Вадим Алексеевич 7 «К» класс iconКоличество, качество и противоположности: вчера, сегодня, завтра
Рискуя с первых строк утратить доверие искушенного читателя, автор вынужден констатировать отсутствие сведений о том, что еще древнегреческие...
Исследовательская работа Комбинаторика: вчера, сегодня, завтра. Автор: Кравченко Вадим Алексеевич 7 «К» класс icon«эксперимент»: вчера, сегодня, завтра… Избранное Под редакцией Б. А. Зельцермана Педагогический центр «Эксперимент»
Б. Зельцерман и др. «Эксперимент»: вчера, сегодня, завтра Избранное. Рига, Педагогический центр «Эксперимент», 2007. – 139 с
Исследовательская работа Комбинаторика: вчера, сегодня, завтра. Автор: Кравченко Вадим Алексеевич 7 «К» класс icon«Государственная Дума вчера,сегодня, завтра…»

Исследовательская работа Комбинаторика: вчера, сегодня, завтра. Автор: Кравченко Вадим Алексеевич 7 «К» класс iconЕлена Николаевна Силуянова в студии. Что вас волнует? На сегодня, на вчера и на завтра
Никита Кричевский: Елена Николаевна Силуянова в студии. Что вас волнует? На сегодня, на вчера и на завтра
Исследовательская работа Комбинаторика: вчера, сегодня, завтра. Автор: Кравченко Вадим Алексеевич 7 «К» класс iconКайрбек Нагуманов Пенсия от детей: вчера – бред, сегодня – в этом что-то есть, завтра – так и будет!
Пенсия от детей: вчера – бред, сегодня – в этом что-то есть, завтра – так и будет!
Исследовательская работа Комбинаторика: вчера, сегодня, завтра. Автор: Кравченко Вадим Алексеевич 7 «К» класс iconОт инстинктов к выбору, смыслу и саморегуляции: психология мотивации вчера, сегодня и завтра
От инстинктов — к выбору, смыслу и саморегуляции: психология мотивации вчера, сегодня и завтра
Исследовательская работа Комбинаторика: вчера, сегодня, завтра. Автор: Кравченко Вадим Алексеевич 7 «К» класс iconАльбер Камю Посторонний
Сегодня умерла мама. А может быть, вчера — не знаю. Я получил из богадельни телеграмму: «Мать скончалась. Похороны завтра. Искренне...
Исследовательская работа Комбинаторика: вчера, сегодня, завтра. Автор: Кравченко Вадим Алексеевич 7 «К» класс iconАльбер Камю. Посторонний
Сегодня умерла мама. А может быть, вчера не знаю. Я получил богадельни телеграмму: "Мать скончалась. Похороны завтра. Искренне соболезнуем"....
Исследовательская работа Комбинаторика: вчера, сегодня, завтра. Автор: Кравченко Вадим Алексеевич 7 «К» класс iconГ. Б. Комарницкий. Мина замедленного действия румынский национализм: вчера, сегодня завтра? Заметки неравнодушного

Разместите кнопку на своём сайте:
ru.convdocs.org


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