На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: shadeofgray, JoeUser
  
> рисование обрамления таблицы в ASCII-art, минимизировать количество операций
    Представьте, что у вас есть задача нарисовать ASCII символами следующее обрамление таблицы
    фыв
    Прикреплённая картинка
    .
    Нарисовать нужно в DOS на assembler такими символами http://en.wikipedia.org/wiki/Box-drawing_character#DOS.
    Основная суть в том, чтобы получить откомпилированный файл как можно меньшего размера, т.е количество операций и вообще данных в исходнике нужно минимизировать.
    На самом деле это лишь часть всего задания, но загвоздка именно в этом.
    Само обрамление я нарисовал, но только символами '=' и '||', т.е без уголочков и крестовин.
    А эти уголочки и крестовины - это в моем алгоритме вырожденный случай, их нужно рисовать отдельно и соответственно код разрастается в полтора раза только из-за них.
    Я не могу ничего придумать, кроме следующего алгоритма (псевдокод на СИ):
    ExpandedWrap disabled
      int arr[][] = {
      {0,0,a}, {0,2,b}, {0,19,c},
      {2,0,d}, {2,2,e}, {2,19,f},
      {19,0,g}, {19,2,h}, {19,19,i}
      };
      for (int i = 0; i < 9; ++i) {
          vga[arr[i][0]][arr[i][1]] = arr[i][2];
      }

    Здесь задано можно сказать отображение (i, j) -> symbol. Мы пробегаемся по этому отображению и рисуем в позиции (i, j) symbol.
    Это довольно стандартный прием. Но из-за этого хардкода этого "отображения" файл вырастает на 50 байт.
    Какие еще можете посоветовать приемы, алгоритм?
    Т.е еще раз, подытожу:
    Нужно поставить в заданных позициях уголочки так, чтобы занимаемое место кода было наименьшим.
    Я думал еще над тем, чтобы найти закономерность в ascii кодах уголочков (на картинке в аттаче эти коды), и тогда не придется хардкодить. Можно было бы составить формулу f, подставлять туда i, а она выдавала бы ascii код i-го уголочка. Но закономерности не вижу.
    Сообщение отредактировано: Dart_Sitius -
      У тебя для таблиц всего двадцать символов, включая прямые участки. Напиши формулу, которая просто будет выдавать уникальный номер символа от 0 до, скажем, до 32. Можно, чтобы одному символу соответствовали несколько номеров. А дальше сделай табличку длиной 32 символа и выбирай из неё нужный код. Это будет компактнее, чем хитрая формула, вычисляющая сам код символа.

      У тебя что, программа длиной всего 200 байт, что тебе лишних 50 байт жалко?
      Кстати, программа не может занимать меньше 512 байт даже на дискете, на жёстком диске соответственно 4096 байт.

      Добавлено
      Ошибся. Всего символов рамочек 40. Но если ты пользуешься только двойной рамкой, то их остаётся одиннадцать. вполне можно разместить в табличку длиной 16.

      Один из вариантов.
      Рамочка в клетке может продолжаться в четырёх направлениях. Записывая имеющиеся направления в виде двоичного числа, получаешь значение от 0 до 15. Четыре из них (1, 2, 4, 8) вообще говоря невозможны, остальные соответствуют пробелу и твоим 11 символам.
      Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
        amk, почти угадали. 190 байт ограничение на всю программу. в этом смысл - бьюсь за каждый байт.
        насчет табличек, я не понял, как их связать еще и с координатами.
        т.е я могу записать символы уголков и крестовин в один массив: db 0C9h,0CBh,0BBh,0CCh,0CEh,0B9h,0C8h,0CDh,0BCh - вот они.
        как мне теперь компактно вывести эти символы именно в нужных координатах? (0,0) (0, 2) ...
        Сообщение отредактировано: Dart_Sitius -
          Цитата
          190 байт ограничение на всю программу

          Смутно подозреваю, что здесь опять неправильно поставлена задача. Потому что на картинке таблица имеет размер 18*6 знакомест, если добавить переводы строк, то получится 120 байт, вызов функции DOS для вывода текста и завершение программы - порядка 10 байт. Так что если компилировать в формат COM, то отведенного объема хватит с лихвой, и еще останется место под пасхальные яйца. Автор, как же на самом деле формулируется задача?
            Действительно, без оригинального ТЗ непонятно что требуется.

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

            Текст надо формировать, соответственно, строками.

            Непонятно в каких координатах нужно выводить текст. Но есть определение arr[][], из которого телепатически следует, что:
            1) Верхняя строка заголовка и левого столбца нумерации по одной свободной ячейке.
            2) На 20-й строке таблица заканчивается очередной рамкой.

            ExpandedWrap disabled
              /* Итого: Строки от 0 до 19 */
               
              for (i = 0; i < 20; i++){
               
              /* Если это 0-я строка, тогда рамка "верхняя" */
                  switch(i){
              /* Устанавливаем коды левой, средней и правой крестовины, и прогон */
                  case 0:
                    l_ch = 201;
                    m_ch = 203;
                    r_ch = 187;
                    s_ch = 205;
                    break;
                  case 2:
                    l_ch = 204;
                    m_ch = 206;
                    r_ch = 185;
                    s_ch = 205;
                    break;
                  case 19:
                    l_ch = 200;
                    m_ch = 202;
                    r_ch = 188;
                    s_ch = 205;
                    break;
                  default:
                    l_ch = 186;
                    m_ch = 186;
                    r_ch = 186;
                    s_ch = 32;
                  }
              /* Столбцы от 0 до 19: */
                for (j = 0; j < 20; j++){
               
              /* Набиваем выводимую строку */
                  switch(j){
                  case 0:
                    *(buf + j) = l_ch;
                    break;
                  case 2:
                    *(buf + j) = m_ch;
                    break;
                  case 19:
                    *(buf + j) = r_ch;
                    break;
                  default:
                    *(buf + j) = s_ch;
                  }
                }
              /* Строка готова. Обнуляем кончик и выводим: */
                *(buf + 20) = 0;
                printf("%s\n", buf);
              }
               
              return 0; /* Everything went OK */

            Осталось только переписать на asm. Думаю, с этим не должно возникнуть проблем.
            Сообщение отредактировано: p1qb0d -
              Гм, действительно, в коде автора таблица имеет размер 20*20 знакомест. Значит, все сложно. Есть идея алгоритма, который берет компактное (n + m + 2 байта) описание любой таблицы:

              В таблице может быть 4 вида текстовых строк: верхняя и нижняя рамка, горизонтальная граница и ячейки. В строке могут быть 4 вида символов: левая и правая рамка, вертикальная граница/пересечение, горизональная линия/пробел. Все возможные варианты символов храним в таблице 4*4 байт. Описание строки таблицы: количество столбцов n (1 байт), затем n байт с ширинами столбцов (без учета границ). Описание столбца таблицы: количество строк m (1 байт), затем m байт с высотами строк (без учета границ). Чтобы не насиловать ОС, выводимые символы можно складывать во временный буфер, а затем печатать сразу всю строку.

              Цикл рисования строки текста принимает тип строки, выводит левую границу, для каждого столбца - нужное количество пробелов/линий плюс (кроме последнего столбца) вертикальную границу/пересечение, правую границу, перевод строки.

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

              Уложить все это в 190 байт - элементарно.
                Хранить 16 байт, если используется 4 байта - слишком шикарно. Лучше в коде этим переменным присваивать константы, потому что код все равно нужно генерить - хоть константу, хоть обращение к ячейке памяти.
                  Спасибо за ответы! Выкладываю пока полное ТЗ:
                  1. Таблица ASCII-символов 16х16, символы по порядку слева направо сверху вниз
                  2. Таблица очерчена символами двойного бордюра
                  3. Сверху и слева от таблицы отображена нумерация столбцов и строк числами от 0 до F.
                  4. Внешние границы также символами двойного бордюра
                  5. Во всех режимах таблица строго посередине экрана
                  выводить лучше напрямую в память (меньше места займет, чем через int 10h)
                  Сейчас буду вникать в ответы
                  Прикреплённая картинка
                  Прикреплённая картинка
                  Сообщение отредактировано: Dart_Sitius -
                    Цитата
                    Хранить 16 байт, если используется 4 байта - слишком шикарно. Лучше в коде этим переменным присваивать константы

                    Выбросить 12 байт данных и 12 байт кода, чтобы вместо них впендюрить, как минимум, 40 байт кода? Ну, не знаю...
                    Сообщение отредактировано: AVA12 -
                      AVA12, p1qb0d, понял ваши идеи. во многом они похожи, и самое главное, отличаются от моей идеи. я выводил не построчно, и поэтому уголки не вписывались в мой алгоритм, а их вывод стоял особняком. если же выводитть построчно, то все гармонично.
                      спасибо, буду пробовать! если возникнут еще идеи - можете сюда их писать.
                        1) switch(i) придется из внешнего цикла перенести во внутренний, если он будет определять s_ch. Если не будет - можно оставить во внешнем, но определение s_ch придется переносить во внутренний цикл (j) полюбому.

                        2) В оба switch нужно добавить case 1: В нем, если i = 1 (или j) И j > 2 (или i), то нужно будет s_ch присвоить более интересное значение от 0 до F. От 0 до 9 легко, нужно только из i (j) вычесть 3 и прибавить 30h. От A до F соответственно прибавлять 41h (судя по картинке ТЗ).

                        3) Заполнение основной таблицы что-то типа s_ch = ((i - 3) << 4) + (j - 3);

                        Но тут еще есть что пооптимизировать...
                        1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                        0 пользователей:


                        Рейтинг@Mail.ru
                        [ Script Execution time: 0,1429 ]   [ 17 queries used ]   [ Generated: 23.05.18, 22:38 GMT ]