НАЙДИ СВОЙ ТАЛАНТВторник, 19.12.2017, 01:18

Приветствую Вас Гость | RSS
Главная | Каталог статей | Регистрация | Вход
Меню сайта

Категории раздела
Мои статьи [7]

Наш опрос
Оцените мой сайт
Всего ответов: 33

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

Форма входа

Главная » Статьи » Мои статьи

Олимпиады по информатике
Занятие первое
 
 
Всем хорошо известно, что представляет собой олимпийское движение. Это спорт! А спорт - это состязание сильнейших. Цель таких состязаний - выявить самого сильного. Это верно и тогда, когда речь идет о предметных олимпиадах, которые имеют уже многолетнюю историю и, даже, являются обязательными для общеобразовательных школ. Спорт, в котором главным объектом является интеллект человека. Содержание задач, предлагаемых ученикам, уже давно вышло за пределы обычной школьной программы. А, следовательно, победителем в таких соревнованиях может стать только тот, кто, как и обычный спортсмен, ежедневно "качает свои интеллектуальные мышцы". Со стороны это может выглядеть, как беспредельная любознательность и, действительно, только она может стать основой для настоящих побед. Но кроме этого необходим еще и титанический труд. И не просто труд, а труд, основанный на знании определенных методов и приемов.

Какие же рекомендации можно дать ученику, решившему попробовать свои силы в олимпиаде по информатике.

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

1. Не имеет смысла браться за решение задачи, если ты не "вчитался" в задание настолько, что тебе на все 100 % понятны все тонкости проблемы, поставленной перед тобой. Очень часто можно видеть, как ученики, едва успев прочитать задание, начинают писать на листочках какие-то команды и торопятся попробовать, как будет работать на компьютере их программа. Конечно, может и повезти - вы видите задачу такого типа, на который вы уже разобрали множество примеров. Но и в этом случае не следует спешить.

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

3. Только на этом этапе начинает работать та часть твоего интеллекта, которая ищет решение. Включаются те "аппараты" мозга, которые идентичны у инженеров и ученых. Это и чистый перебор вариантов, и интуиция. Могут встретиться такие задачи, для решения которых необходим настоящий талант. И здесь единственным напутствием будет: пробуйте, не отчаивайтесь, волевым усилием напрягайте "мышцы" вашего мозга. Для озарения необходима предпосылка - целенаправленная работа.

4. Выработай сам для себя алгоритмический язык. Конечно, желательно знать язык блок - схем. Но это уже следующий этап - оформление работы. И тебе может быть даже легче писать сразу текст программы на каком-нибудь языке программирования. Речь сейчас о другом. Очень трудно представить все решение чисто в воображении. Необходимы какие-нибудь опорные сигналы - кружочки, черточки. Это очень помогает последовательно рассуждать. Последовательное рассуждение - это выстраивание цепочек из таких значков. Когда будут увязаны между собой все звенья одной "большой цепи", это и будет алгоритм решения задачи.

5. Конечно, уже на этапе составления алгоритма предполагается, что вы знаете набор команд исполнителя. Но только после составления алгоритма программы, по настоящему вступает в силу знание операторов конкретного языка программирования. Чем глубже и шире (количество известных вам команд) вы знаете язык, тем легче вам будет перевести алгоритм на язык программирования. Поэтому вы должны постоянно и неустанно совершенствоваться в этом вопросе. В настоящий момент почему-то выдвинуто требование проводить олимпиады на языке Turbo Pascal. И мы будем разбирать примеры, используя этот язык. Но это не принципиальное требование. Даже можно сказать, что если решение выполнено более "примитивными" средствами, то для этого могло понадобиться более оригинальное мышление. К тому же старый добрый Бейсик продолжает жить в системе программирования Visual Basic.

Давайте попробуем применить на практике рассмотренные выше рекомендации.

Задача
Ребус. Написать программу, в которой требуется заменить буквы цифрами так, чтобы получилось верное равенство. Найти количество всех возможных вариантов решений и максимальное значение из них. (10 балов).
МУХА
+
МУХА
СЛОН

Формат выходного файла(Ребус.OUT):
4865
+
4865
9730
 
1 этап. Все ли вам понятно в условии задачи?
Подобные задачи обычно предлагают учащимся учителя математики во время различных конкурсов или предметных декад. Перед нами головоломка: нам дан пример на сложение, в котором цифры заменены(зашифрованы) буквами. Одинаковые буквы скрывают одинаковые цифры. В данном случае мы имеем сложение двух одинаковых четырехзначных чисел и результат - так же четырехзначное число. При этом в слагаемых и сумме нет одинаковых цифр. Обычно такие задачи решают путем подбора и логических рассуждений. Такие задачи могут иметь много различных решений. В нашем случае: необходимо составить программу, которая сама найдет общее количество решений и при этом укажет наибольшее из них.
2 этап. Как же заставить компьютер выполнять все эти действия: находить решения, подсчитывать их количество и при этом выбрать наибольшее из них? В данном случае можно было бы предложить следующий план действий:
- перебирать все варианты возможных слагаемых;
- составлять из них суммы;
- проверять суммы на "неодинаковость" цифр в сумме и слагаемых;
- завести переменную для подсчета количества сумм, удовлетворяющих предыдущему условию;
- сравнивая каждую сумму с предыдущей, производить выбор наибольшей.
После выполнения этих действий необходимо записать полученный результат в отдельный файл.
Что значит - перебирать все варианты возможных слагаемых? Это можно сделать путем перебора всех вариантов возможных цифр в четырехзначном числе. Наша задача облегчена тем, что оба слагаемых одинаковы и сумма тоже четырехзначное число, т. е. первая цифра в слагаемых не может быть больше четырех.
Для перебора вариантов возможных цифр можно составить конструкцию из вложенных циклов для каждой цифры. При этом для первой цифры необходим параметр повторения от 1 до 4, а для остальных от 0 до 9.
 
 


3 этап. После проделанного только что разбора решения, у вас мог появиться следующий схематический алгоритм решения данной задачи:

Название программы
Описание переменных
    Параметры циклов 
    Сумма
    Макс, кол-во и др.
Начало программы
Очистка экрана
Макс = 0
Кол = 0
циклы
a от 1 до 4
 b от 0 до 9
  с от 0 до 9
   d от 0 до 9
    Составлять суммы (цифры должны быть разные)
    Проверять, чтобы в сумме цифры тоже были разными и не
    совпадали с цифрами слагаемых
    Выбор наибольшей из удовлетворяющих другим условиям
    Подсчет количества сумм
Запись ответа в отдельный файл
Конец программы
 
4 этап. Так как нам не требуется отдельно составить алгоритм, оформленный по всем правилам алгоритмического языка, то можно сразу обратиться к языку программирования. Как мы уже говорили - это будет Turbo Pascal.

Приводим ниже текст готовой программы:
program muxa;
uses Crt;
var
   i,a,b,c,d: integer;
  m,s,max,kol: Integer;
  f: text;
  ss,as,bs,cs,ds: string;
label 1;
begin
  ClrScr;
  max := 0;
  kol := 0;
    for a:=1 to 4 do 
    begin
     for b:=0 to 9 do
     begin
      for c:=0 to 9 do
      begin
       for d:=0 to 9 do
       begin
        if (a=b) or (a=c) or (a=d) or (b=c) or (b=d) or (c=d) then goto 1;
        s:=2*(d+c*10+b*100+a*1000);
        str(s,ss);
        str(a,as);
        str(b,bs);
        str(c,cs);
        str(d,ds);
        if (ss[1]<>ss[2]) and (ss[1]<>ss[3]) and (ss[1]<>ss[4])
          and (ss[2]<>ss[3]) and (ss[2]<>ss[4]) and(ss[3]<>ss[4])
          then begin
           for i:=1 to 4 do
            begin
             if (ss[i]=as) or (ss[i]=bs) or (ss[i]=cs) or
            (ss[i]=ds) then goto 1;
           end;
           if s>max then begin max:=s; end;
           kol:=kol+1;
           end;
        1:
        end; 
     end; 
   end;
end;
m:=max div 2;
Assign(f,'Ребус.out');
Rewrite(f);
WriteLn(' ',m);
WriteLn('+');
WriteLn(' ',m);
WriteLn('-------');
WriteLn(' ',max);
Writeln('Общее количество решений: ',kol);
WriteLn(f,' ',m);
WriteLn(f,'+');
WriteLn(f,' ',m);
WriteLn(f,'-------');
WriteLn(f,' ',max);
Writeln(f,'Общее количество решений: ',kol);
Close(f);
readln;
end.

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

Желаем удачи!
 
Категория: Мои статьи | Добавил: iskatel (17.11.2009)
Просмотров: 1009 | Рейтинг: 0.0/0
Всего комментариев: 0
Имя *:
Email *:
Код *:
Поиск

Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz


  • Copyright MyCorp © 2017
    Бесплатный хостинг uCoz