На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! Оставь надежду всяк сюда входящий
1) На раздел распространяются все правила форума.
2) Ответы на головоломки необходимо давать только в теге SPOILER. Сообщения в обход этого правила будут удаляться. Постоянное
нарушение данного пункта правил, повлечет за собой наказание.
3) Автор темы должен указать, известно ли ему решения задачи и сроки в которые он опубликует решение.Рекомендуется вести список отгадавших в первом сообщении.
4) При создании новой темы, в описании или в самом названии четко укажите разновидность задачи.
5) Полная версия правил раздела, находится в теме правила раздела.
Модераторы: Братец Лис
Страницы: (6) « Первая ... 4 5 [6]  все  ( Перейти к последнему сообщению )  
> головоломки на написание алгоритма
    Наконец-то разобрался. Времени ушло больше, чем на написание.

    Проблема действительно была в проге сложения: она неверно считала 90000 + 21105. Пришлось поправить подсчёт кол-ва цифр в результирующем числе.

    Итого, функция сложения в проге сложения выглядит так:

    Скрытый текст
    ExpandedWrap disabled
      // *** собственно, сложение: начало
      int summ(unsigned char FirstNum[101], unsigned char SecondNum[101], unsigned char Result[201])
      {
          unsigned char tmp, max;
       
          if (FirstNum[100] >= SecondNum[100]) max = FirstNum[100];
          else max = SecondNum[100];
       
          // массивы идут от младших разрядов к старшим
          // складываем пары цифр и кладём сумму в Result, а "в уме"- в tmp
       
          tmp = 0;
          for(int i=0; i <= max; i++)
          {
              tmp = FirstNum[i] + SecondNum[i] + tmp;
       
              Result[i] = div(tmp,10).rem;
              tmp = div(tmp,10).quot;
          }
          Result[max+1] = tmp;
          if(tmp>0) Result[200] = max+2;
          else
          {
              if(Result[max]>0) Result[200] = max+1;
              else
              {
                  Result[200] = max;
              }
          }
       
          return 0;
      }
      // *** собственно, сложение: конец



    А прога умножения(полностью) выглядит так

    Скрытый текст

    ExpandedWrap disabled
      #include <stdio.h> // для работы с файлами и для sprintf
      #include <stdlib.h> // для div()
       
      // *** получаем инфу из файла: начало
      int get_input_data(char *input_name, unsigned char FirstNum[101], unsigned char SecondNum[101])
      {
          FILE *file;
          unsigned char Tmp[100];
          unsigned char c;
       
          // открываем файл для чтения
          file = fopen(input_name, "r");
          // w- write, r- read, a- append
          
          // если открыть файл не удалось
          if (file == NULL) return -1;
       
          // пропускаем любое кол-во не-цифр
          bool flag= false;
          do
          {
              c = fgetc(file);
              if(feof(file)){fclose(file);return -1;}
       
              if (c < 58 &&  c >= 48 )
              {
                  // заносим инфу в массив
                  Tmp[0] = c-48;
                  flag = true;
              }
          }
          while (!flag);
       
          //считываем все подряд идущие цифры до не-цифры
          int i = 0;
          do
          {
              c = fgetc(file);
              if(feof(file)){fclose(file);return -1;}
       
              if (c < 58 &&  c >= 48 && i < 100)
              {
                  // заносим инфу в массив
                  i++;
                  Tmp[i] = c-48;
              }
              else
              {
                  flag = false;
              }
          }
          while (flag);
          // лишние цифры(сверх 100) просто проигнорируются
       
          // заносим Tmp в FirstNum:
          for(int k=0; k<=i; k++) FirstNum[k]= Tmp[i-k];
          FirstNum[100] = i+1;
       
          // пропускаем любое кол-во не-цифр
          do
          {
              c = fgetc(file);
              if(feof(file)){fclose(file);return -1;}
       
              if (c < 58 &&  c >= 48 )
              {
                  // заносим инфу в массив
                  Tmp[0] = c-48;
                  flag = true;
              }
          }
          while (!flag);
       
          //считываем все подряд идущие цифры до не-цифры
          i = 0;
          do
          {
              c = fgetc(file);
              if(feof(file)){fclose(file);return -1;}
       
              if (c < 58 &&  c >= 48 && i < 100)
              {
                  // заносим инфу в массив
                  i++;
                  Tmp[i] = c-48;
              }
              else
              {
                  flag = false;
              }
          }
          while (flag);
          // лишние цифры(сверх 100) просто проигнорируются
       
          // заносим Tmp в SecondNum:
          for(int k=0; k<=i; k++) SecondNum[k]= Tmp[i-k];
          SecondNum[100] = i+1;  
       
          // закрываем файл
          fclose(file);
       
          // 0- код успешного завершения
          return 0;
      }
      // *** получаем инфу из файла: конец
       
      // *** выводим инфу в файл: начало
      int put_input_data(char *output_name, unsigned char FirstNum[101], unsigned char SecondNum[101], unsigned char Result[201])
      {
          FILE *file;
       
          file = fopen(output_name, "w"); // открываем файл для записи
       
          // если открыть файл не удалось
          if (file == NULL) return -1;
       
          for (int i= FirstNum[100]-1; i>=0; i--) fputc(FirstNum[i]+48,file);
          fputc('\n',file);
       
          fputc('*',file);
          fputc('\n',file);
       
          for (int i= SecondNum[100]-1; i>=0; i--) fputc(SecondNum[i]+48,file);
          fputc('\n',file);
       
          fputc('=',file);
          fputc('\n',file);
       
          for (int i= Result[200]-1; i>=0; i--) fputc(Result[i]+48,file);
          fputc('\n',file);
       
          fputc('\n',file);
          fclose(file);
       
          return 0;
      }
      // *** выводим инфу в файл: конец
       
      // *** наращивание второго числа на первое: начало
      int summ(unsigned char FirstNum[201], unsigned char SecondNum[201])
      {
          unsigned char tmp, max, Result[201]={}; // в ячейке 200 хранится кол-во цифр числа
       
          if (FirstNum[200] >= SecondNum[200]) max = FirstNum[200];
          else max = SecondNum[200];
       
          // конкретно в данной проге эта функция используется так, что результат не вылезет за границы
       
          tmp = 0;
          for(int i=0; i <= max; i++)
          {
              tmp = FirstNum[i] + SecondNum[i] + tmp;
       
              Result[i] = div(tmp,10).rem;
              tmp = div(tmp,10).quot;
          }
          Result[max+1] = tmp;
          if(tmp>0) Result[200] = max+2;
          else
          {
              if(Result[max]>0) Result[200] = max+1;
              else
              {
                  Result[200] = max;
              }
          }
       
          for(int i=0; i <= 200; i++) SecondNum[i] = Result[i];
       
          return 0;
      }
      // *** наращивание второго числа на первое: конец
       
      // *** собственно, умножение: начало
      int multiplication(unsigned char FirstNum[101], unsigned char SecondNum[101], unsigned char Result[201])
      {
          unsigned char tmp, Temp[201];  // в ячейке 200 хранится кол-во цифр числа
       
          // массивы идут от младших разрядов к старшим
          // каждую цифру второго числа умножаем на первое число
          // получившийся в Temp результат суммируем в Result
       
          for(int i=0; i < SecondNum[100]; i++)
          {
              tmp = 0;
              for(int m=0; m <= 200; m++) Temp[m] = 0;
       
              // каждую цифру второго числа умножаем на первое число
              for(int k=0; k < FirstNum[100]; k++)
              {
                  tmp = (FirstNum[k]*SecondNum[i]+tmp);
                  Temp[k +i] = div(tmp,10).rem; // +i даёт нужный сдвиг
                  tmp = div(tmp,10).quot;    
              }
              Temp[FirstNum[100] +i] = tmp;
              if(tmp>0) Temp[200] = FirstNum[100]+1 +i;
              else Temp[200] = FirstNum[100] +i;
       
       
       
              // получившийся в Temp результат суммируем в Result
              summ(Temp, Result);
          }
       
          return 0;
      }
      // *** собственно, умножение: конец
       
      int main()
      {
          unsigned char FirstNum[101]={}, SecondNum[101]={}; // в ячейке 100 хранится кол-во цифр числа
          unsigned char Result[201]={}; // в ячейке 200 хранится кол-во цифр числа
       
          // получаем инфу из файла
          get_input_data("input.txt", FirstNum, SecondNum);
       
          // собственно, умножение
          multiplication(FirstNum, SecondNum, Result);
       
          // выводим инфу в файл
          put_input_data("output.txt", FirstNum, SecondNum, Result);
       
      }



    И теперь я подсмотрю исходник того, кто выполнил это задание первым :)

    Добавлено
    Цитата _lcf_ @
    Скрытый текст


    Нифига непонятно. Это на чём вообще написано? :-?

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

    Добавлено
    _lcf_, буду признателен за разъяснения.
    Сообщение отредактировано: ya2500 -
    "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
    "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
      План на следующие выходные:

      1) Сделать деление 100-значных целых чисел. Результат может получиться с плавающей точкой, точность результата- до 100 знаков после запятой, остальное- отбрасывается.

      2) Сделать сложение, умножение, вычитание 100-значных чисел с плавающей точкой(то есть, число представляет из себя строку, длиной до 100 символов, один из которых может быть плавающей точкой).

      И, если успею:
      3) Сделать деление 100-значных чисел с плавающей точкой.

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

      Цитата ya2500 @
      Дано арифметическое выражение, длиной не более 30 символов, состоящее из цифр и знаков


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

      Добавлено
      Но, пока, слишком далеко забегать не буду И после выражения, возьмусь, пожалуй, за "быков и коров"

      Цитата ya2500 @
      Написать программу, подбирающую "секретный пароль" из 15 цифр, получая после каждой попытки информацию о кол-ве быков и коров.


      Цитата ya2500 @
      Как вариант, можно написать прогу просто для игры в "быки и коровы".
      "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
      "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
        Цитата ya2500 @
        Интересует два момента: разобраться, как оно вычисляет результат И разобраться, как оно считает кол-во разрядов результирующего числа.

        А зачем там что-то особо считать? Полагай, что результат сложения на 1 длиннее самого длинного слагаемого. Если первая цифра результата получится 0 - убираешь её, и всё.
        С умножением похоже - полагаешь длину равной сумме длин множителей, и если первая цифра ноль - убираешь его.
        Подпись была включена в связи с окончанием срока наказания
          Цитата OpenGL @
          А зачем там что-то особо считать? Полагай, что результат сложения на 1 длиннее самого длинного слагаемого. Если первая цифра результата получится 0 - убираешь её, и всё.
          С умножением похоже - полагаешь длину равной сумме длин множителей, и если первая цифра ноль - убираешь его.


          Я тоже так думал. Но, чтобы работало нормально, пришлось в сложении две последние цифры отслеживать. Хотя.. дело, видимо, в том, что я неверно посчитал (номер последняя цифра +1), из-за того, что в c++ массивы начинаются с нулевого индекса.

          Цитата ya2500 @
          План на следующие выходные:


          То есть, на понедельник, 17-го.
          "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
          "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
            Цитата ya2500 @
            Хотя.. дело, видимо, в том, что я неверно посчитал (номер последняя цифра +1), из-за того, что в c++ массивы начинаются с нулевого индекса.


            Нет, дело не могло быть в этом.. ведь 99*99 считало нормально и 12345*9 считало нормально и кучу других примеров считало нормально и только на 9*12345 почему-то проглатывало старшую цифру.

            Цитата ya2500 @
            чтобы работало нормально, пришлось в сложении две последние цифры отслеживать.

            :scratch:

            Но некогда в этом ковыряться. Буду двигаться дальше И помнить о том, как важно хорошо тестить проги И сожалеть о том, что нет на это времени.
            "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
            "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
              Цитата ya2500 @
              План на следующие выходные:
              ...
              3) Сделать деление 100-значных чисел с плавающей точкой.


              Сейчас пилю класс больших чисел myNum(могут быть со знаком и с плавающей точкой), с соответствующими операциями над ними. Похоже, на это несколько выходных уйдёт(благо, они сейчас часто случаются))
              "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
              "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                Попутно обдумайте применение их для расширения на: комплексные числа, матрицы с такими числами. ;)
                  ф топку
                  Таки 1 час каждый выходной(которых теперь будет не так уж много(( хочу тратить на освоение "больших языков", а именно- c++

                  Цитата ya2500 @
                  вскользь упомянуты некоторые из ресурсов, на которых можно найти годные задачи на программирование

                  Цитата ya2500 @
                  Цитата
                  Даны два целых положительных числа, длиной не более 100 цифр каждое. Вычислить произведение этих чисел. И входные и выходные данные должны храниться с абсолютной точностью.

                  - подразумевается, что входные данные берутся из одного файла, а выходные данные записываются в другой файл.

                  - ну вот такая простая задачка, для начала.


                  Цитата ya2500 @
                  Задачку эту я выделил из более сложной:


                  Цитата Славян @
                  Большого смысла в 30 символах не вижу: всё равно потянет написать простенький парсер...


                  Надо бы эти числа(100, 30) хранить в константах.

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

                  ===

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


                  ===

                  Случайно раскопал древнюю книжку "Программирование игр и головоломок", автор Жан Арсак, задания рассчитаны на комп, не имеющий графического монитора. Вот, думаю, лучше пороюсь-ка я для начала в ней.

                  Чтобы начать с чего-нить простого и относительно увлекательного.
                  Сообщение отредактировано: ya2500 -
                  "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                  "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                    Блин, ерунда какая-то. Надо остановиться и хорошо подумать.
                    "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                    "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                      Цитата ya2500 @
                      _lcf_, буду признателен за разъяснения.

                      умножение столбиком! :lool: :lool:
                        Открылась регистрация на международный чемпионат по спортивному программированию — Яндекс.Алгоритм 2018:
                        https://academy.yandex.ru/events/algorithm/2018/#desc

                        подробный разбор задач финала Яндекс.Алгоритм 2017:
                        https://habrahabr.ru/company/yandex/blog/334250/
                        "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                        "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                        1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                        0 пользователей:


                        Рейтинг@Mail.ru
                        [ Script Execution time: 0,1444 ]   [ 14 queries used ]   [ Generated: 25.05.18, 20:40 GMT ]