[Logo] Форум DL
  [DL]  Back to home page 
Forum Index ->Учебный процесс ГГУ/СШ 27 ->Проектирование цифровых систем
Author Message
Mihail Dolinskiy

Topics: 1985
Messages: 47299

My Profile
Новинка сезона

Итак вводится новый вид учебной деятельности, который также будет оцениваться бонусными баллами.

Каждую неделю будет предлагаться НОВАЯ задача с решением.
Любой желающий может написать БОЛЕЕ КРАСИВОЕ РЕШЕНИЕ и также выложить его в форуме.
Победитель (победители) получают бонусные баллы.

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

Какие параметры, по-моему, влияют на красоту для программ:

- читабельность и понятность решения
- минимальное количество строк в программе (с разумным числом операторов в строке)
- минимальное количество вложенных циклов
- минимальное количество операторов условия
...

Какие параметры, по-моему, влияют на красоту для схем устройств:
- читабельность и понятность схемы (симметричность?)
- минимальное количество корпусов
- минимальное количество "приведенных вентилей"
- минимальное количество корпусов на самом длинном пути от входов к выходам
...

Поощряется предложение СВОИХ задач в качестве "задач недели".
Mihail Dolinskiy

Topics: 1985
Messages: 47299

My Profile
Первая задача (на период с 16 по 25 января включительно).

В курсе она стоит как задача на программирование на Паскале.
Для проверки своих идей решений Вы можете там сдавать программы на языках Pascal и C++.

Далее нужно установить аналогичную задачу (получив отдельные баллы за установку новой задачи) для C-MPA, или ассемблера Intel 86 (использовать запрет на другие расширения) или на проектирование схемы такого устройства.

Фактически проводится ТРИ КОНКУРСА (за победу в каждом из которых начисляются свои бонусные баллы)
- для программ на C-MPA
- для программ на ассемблере Intel 8086
- для схем цифровых устройств.

Решения (исходные тексты программ или рисунки схем) выкладывать в ответе на это сообщение с ОБЯЗАТЕЛЬНЫМ ОПИСАНИЕМ ИДЕИ решения. Не забудьте указать свои фамилию, имя и группу.

http://dl.gsu.by/task.jsp?nid=305180&cid=595

Задача Число e

Выведите в выходной файл округленное до n знаков после десятичной точки число e. Число e, округленное до 25-ти знаков после десятичной точки, равно 2.7182818284590452353602875.

Формат ввода:
Первая строка входного файла содержит целое число n (0 <= n <= 25).


Идея решения и текст программы Котова Артема (ПМ-11, январь 2009):


Сначала удаляем в исходном числе точку, потом формируем новую строку до символа n+1 включительно. Если символ n+2 принадлежит отрезку 5..9, тогда к символу n+1 прибавляем еденицу, а если символ n+1 равен 9, тогда присваеваем ему значение ноль.
После, если длина нового числа больше 1, м\у 1 и 2 символами вставляем "."
var
  n,i : byte;
  p,f : string;
begin
  assign(input,'enumber.in'); reset(input);
  assign(output,'enumber.out'); rewrite(output);
  f:= '2.7182818284590452353602875';
  delete(f,pos('.',f),1);
  readln(n);
  p:= '';
  for i:= 1 to n+1 do p:= p + f[i];
  if (f[i+1] in ['5'..'9']) and ((i+1) <= length(f)) then
    begin
      if p[i] <> '9' then p[i]:= chr(ord(p[i])+1)
                     else p[i]:= '0';
    end;
  if length(p) > 1 then insert('.',p,2);
  writeln(p);
  Close(input);
  Close(output);
end.


Mihail Dolinskiy

Topics: 1985
Messages: 47299

My Profile
К сожалению, первую задачу делать никто не стал, хотя в курсе работали очень многие. Тем не менее - вторая задача на период 26 января - 1 февраля.

Задача Анаграммы

Условие: Cтрока S1 называется анаграммой строки S2, если она получается из S2 перестановкой символов.
Даны строки S1 и S2. Напишите программу, которая проверяет, является ли S1 анаграммой S2.

Алгоритм решения (Бакунов Максим, ПО-11):
Смысм состоит в том, чтобы строку S1 разбить на отдельные буквы и записать кол-во одинаковых и различных букв и массив(a[1]=2, т.е. в слове находится две буквы "а"). Так же поступить и со второй строкой. В результате сравнить соответствующие номера 2-ух массивов.
Замечание:Положение букв в 2-ух массивах должно быть одинаковое, т.е. если в первом массиве a[1] – это буква «a», то и во втором a[1] – тоже должен быть «a».

program v1;
var
 a,a1    : array[1..26] of integer;
 i,max,k : longint;
 s,s1,s2 : string;
 pro     : real;
 begin
  assign(input, 'anagram.in'); reset(input);
  assign(output,'anagram.out'); rewrite(output);
  readln(s);
  readln(s1);
 for i:=1 to length(s) do
 begin
  if (s[i]='A')or(s[i]='a') then  a[1]:=a[1]+1;
  if (s[i]='Q')or(s[i]='q') then  a[2]:=a[2]+1;
  if (s[i]='W')or(s[i]='w') then  a[3]:=a[3]+1;
  if (s[i]='E')or(s[i]='e') then  a[4]:=a[4]+1;
  if (s[i]='R')or(s[i]='r') then  a[5]:=a[5]+1;
  if (s[i]='T')or(s[i]='t') then  a[6]:=a[6]+1;
  if (s[i]='Y')or(s[i]='y') then  a[7]:=a[7]+1;
  if (s[i]='U')or(s[i]='u') then  a[8]:=a[8]+1;
  if (s[i]='I')or(s[i]='i') then  a[9]:=a[9]+1;
  if (s[i]='O')or(s[i]='o') then  a[10]:=a[10]+1;
  if (s[i]='P')or(s[i]='p') then  a[11]:=a[11]+1;
  if (s[i]='S')or(s[i]='s') then  a[12]:=a[12]+1;
  if (s[i]='D')or(s[i]='d') then  a[13]:=a[13]+1;
  if (s[i]='F')or(s[i]='f') then  a[14]:=a[14]+1;
  if (s[i]='G')or(s[i]='g') then  a[15]:=a[15]+1;
  if (s[i]='H')or(s[i]='h') then  a[16]:=a[16]+1;
  if (s[i]='J')or(s[i]='j') then  a[17]:=a[17]+1;
  if (s[i]='K')or(s[i]='k') then  a[18]:=a[18]+1;
  if (s[i]='L')or(s[i]='l') then  a[19]:=a[19]+1;
  if (s[i]='Z')or(s[i]='z') then  a[20]:=a[20]+1;
  if (s[i]='X')or(s[i]='x') then  a[21]:=a[21]+1;
  if (s[i]='C')or(s[i]='c') then  a[22]:=a[22]+1;
  if (s[i]='V')or(s[i]='v') then  a[23]:=a[23]+1;
  if (s[i]='B')or(s[i]='b') then  a[24]:=a[24]+1;
  if (s[i]='N')or(s[i]='n') then  a[25]:=a[25]+1;
  if (s[i]='M')or(s[i]='m') then  a[26]:=a[26]+1;
  end;

 for i:=1 to length(s1) do
 begin
  if (s1[i]='A')or(s1[i]='a') then  a1[1]:=a1[1]+1;
  if (s1[i]='Q')or(s1[i]='q') then  a1[2]:=a1[2]+1;
  if (s1[i]='W')or(s1[i]='w') then  a1[3]:=a1[3]+1;
  if (s1[i]='E')or(s1[i]='e') then  a1[4]:=a1[4]+1;
  if (s1[i]='R')or(s1[i]='r') then  a1[5]:=a1[5]+1;
  if (s1[i]='T')or(s1[i]='t') then  a1[6]:=a1[6]+1;
  if (s1[i]='Y')or(s1[i]='y') then  a1[7]:=a1[7]+1;
  if (s1[i]='U')or(s1[i]='u') then  a1[8]:=a1[8]+1;
  if (s1[i]='I')or(s1[i]='i') then  a1[9]:=a1[9]+1;
  if (s1[i]='O')or(s1[i]='o') then  a1[10]:=a1[10]+1;
  if (s1[i]='P')or(s1[i]='p') then  a1[11]:=a1[11]+1;
  if (s1[i]='S')or(s1[i]='s') then  a1[12]:=a1[12]+1;
  if (s1[i]='D')or(s1[i]='d') then  a1[13]:=a1[13]+1;
  if (s1[i]='F')or(s1[i]='f') then  a1[14]:=a1[14]+1;
  if (s1[i]='G')or(s1[i]='g') then  a1[15]:=a1[15]+1;
  if (s1[i]='H')or(s1[i]='h') then  a1[16]:=a1[16]+1;
  if (s1[i]='J')or(s1[i]='j') then  a1[17]:=a1[17]+1;
  if (s1[i]='K')or(s1[i]='k') then  a1[18]:=a1[18]+1;
  if (s1[i]='L')or(s1[i]='l') then  a1[19]:=a1[19]+1;
  if (s1[i]='Z')or(s1[i]='z') then  a1[20]:=a1[20]+1;
  if (s1[i]='X')or(s1[i]='x') then  a1[21]:=a1[21]+1;
  if (s1[i]='C')or(s1[i]='c') then  a1[22]:=a1[22]+1;
  if (s1[i]='V')or(s1[i]='v') then  a1[23]:=a1[23]+1;
  if (s1[i]='B')or(s1[i]='b') then  a1[24]:=a1[24]+1;
  if (s1[i]='N')or(s1[i]='n') then  a1[25]:=a1[25]+1;
  if (s1[i]='M')or(s1[i]='m') then  a1[26]:=a1[26]+1;
  end;

  k:=0;
    for i:=1 to 26 do
     if a[i]<>a1[i] then
       k:=k+1;
     if k=0 then
      writeln('Yes')
      else
      writeln('No');
  
  close(input); close(output);  
 end.


Mihail Dolinskiy

Topics: 1985
Messages: 47299

My Profile
Задача
"Клавиша Shift" 78313
У Коли беда. На его новенькой клавиатуре перестала работать клавиша Shift. За время использования клавиатуры Коля всего лишь набрал свое сочинение по английскому языку, используя при этом обычную английскую раскладку и только левый Shift (Коля пока еще достаточно плохо набирает на клавиатуре). При покупке клавиатуры Коле сообщили, что каждая клавиша выдерживает нажатий.
Теперь Коле интересно, какое минимальное число раз он мог нажать Shift, чтобы набрать тот же текст, чтобы знать может ли он потребовать замену клавиатуры. При написании Коля мог бы зажимать Shift и поочередно нажимать несколько других клавиш, не отпуская Shift, и это считалось бы одним нажатием. Клавишей Caps Lock Коля не пользуется принципиально.

Идея и текст решения Василия Пузана (ПО-11)

Алгоритм заключается в том, что все строки которые начинаются с новой строки вставляем в одну(это можно сделать потому что при переходе на новую строку нажатие шифта не cчитывается)....получается очень длинная строка с пробелами, после чего пробелы удаляем. Затем для того чтобы проверился так же и первый символ(нажат Шифт или нет) вставляем в начало строки любой маленький символ. После чего считаем кол-во нажатых шифтов если предыдущий маленький, а текущий большой => k:=k+1;


{$R+}

{$APPTYPE CONSOLE}

var
  i,j,n,k,q : longint;
  s,s2,p : WideString;
  s1: array [1..100] of string;
begin
assign(input,'shift.in'); reset(input);
assign(output,'shift.out'); rewrite(output);
i:=1;
while not eof(input) do    {чтение пока не конец файла}
  begin
   readln(s1[i]); inc(i);end;
   k:=0; q:=i;
p:='QWERTYUIOPASDFGHJKLMNBVCXZ';
for j:=1 to q do begin
  s:=s+s1[j];         {все в оджну строку }
end;
n:=length(s);
for i:=1 to 100 do
  begin
  n:=0;
  n := pos(' ',s);
  if n<>0 then delete(s,n,1);{поиск и удаление пробелов}
  end;
insert('q',s,1); {вставка символа в нижнем регистре}
for i:=2 to length(s) do
  if (pos(s[i],p)<>0) and(pos(s[i-1],p)=0) then inc(k);{поиск и подсчет нажатий}

   writeln(k);
close(input);
close(output);
end.

Bogdan Viktorovich

Topics: 0
Messages: 6

My Profile
Поздновато, конечно, но всё же а вдруг... =)

В задаче "анаграммы" само собой напрашивается упрощение многоэтажных ифов в работу с двумя массивами

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void sort(char* s, long r) {
  long* n = (long*)malloc(256*sizeof(long));
  memset(n, 0, 256*sizeof(long));
  for (int i=0; i<r; i++)
    n[s[i]]++;
  char* ss = s;
  for (int i=0; i<256; i++)
    for (int j=0; j<n[i]; j++)
      *(ss++) = (char)i;
}

void main() {
  char* s1 = (char*)malloc(10000001);
  char* s2 = (char*)malloc(10000001);
  long n1=0, n2=0;
  FILE* in = fopen("anagram.in", "r");
  FILE* out = fopen("anagram.out", "w");
  fgets(s1, 100001, in);
  fgets(s2, 100001, in);
  fclose(in);
  if (strlen(s1)!=strlen(s2))
    fprintf(out, "NO\n");
  else {
    sort(s1, strlen(s1));
    sort(s2, strlen(s2));
    long sl = strlen(s1);
    for (int i=0; i<sl; i++)
      if (s1[i]!=s2[i]) {
        fprintf(out, "NO\n");
        fclose(out);
        free(s1);
        free(s2);
        return;
      }
    fprintf(out, "YES\n");
  }
  fclose(in);
  free(s1);
  free(s2);
} 


Метод sort - сортировка строки подсчётом (вроде бы...), по сути то же самое, только компактнее. И ещё остаётся пространство для манёвра.
Mihail Dolinskiy

Topics: 1985
Messages: 47299

My Profile
Лучше поздно, чем никогда.
Викторович Богдан +5 бонусных баллов.
Сортировка подсчетом в этой задаче и по-моему "красивее", чем исходный вариант решения.

Конкурс продолжается. Принимаются новые решения по этой и другим предложенным задачам, равно как и новые задачи.
 
Forum Index ->Учебный процесс ГГУ/СШ 27 ->Проектирование цифровых систем
Time:0,031