Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Получение значения разряда десятичного числа 
:(
    Опции темы
Matrex
Дата 6.4.2009, 16:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 96
Регистрация: 31.1.2006

Репутация: нет
Всего: 2



Коллеги, помогите с алгоритмом функции, для получения значения разряда десятичного числа. Т.е. 

myinttostr(235,0) результат =5
myinttostr(235,1) результат =3
myinttostr(235,2) результат =2

Проблема в том, что допускается использовать только операторы +, -, if, goto, and, xor, or и операции сдвига.

Да, это не задача для ВУЗа - в последующем этот алгоритм будет адаптирован к ассемблеру микроконтроллера PIC16F84 – поэтому такие ограничения по операциям.

PM MAIL   Вверх
Pavia
Дата 6.4.2009, 16:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 418
Регистрация: 6.12.2008

Репутация: 11
Всего: 12



А сразу хранить числа в 10 формате smile не предлогать?

Алгоритм простой
b:=a/10; делем на цело
с:=a-b*10  получаем остаток
goto к следующему разряду

деление на константу легко заменяется на умножение сдвиги и сложения.
Алгоритм лучше прочитать у Агнера Фога. Просто он у него он полностью расписан.

http://www.agner.org/optimize/optimizing_assembly.pdf

PM MAIL   Вверх
Matrex
Дата 6.4.2009, 16:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 96
Регистрация: 31.1.2006

Репутация: нет
Всего: 2



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

По поводу Агнера Фога - он использует уножение... Правда умножение можно заменить сложением... Будем посмотреть...

А есть другие соображения?
PM MAIL   Вверх
Akina
Дата 6.4.2009, 17:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454



А объём дополнительной памяти? критично? 

В крайнем случае нечто типа решения "влоб":
Код

if arg2<2 goto l3
if arg1<200 goto l1
return 2
l1:
if arg1<100 goto l2
return 1
l2:
return 0
l3:
if arg1<100 goto l4
arg1=arg1-100
goto l3
l4:
if arg2=0 goto l999
if arg1<90 goto l5
return 9
l5:
...



--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
Matrex
Дата 6.4.2009, 21:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 96
Регистрация: 31.1.2006

Репутация: нет
Всего: 2



Насчет памяти для конкретно этого приложения не критично, поэтому решение "в лоб" допустимо. Я о чем то подобном думал – такая реализация относится к категории «от отчаяния» smile

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

PM MAIL   Вверх
maxim1000
Дата 6.4.2009, 21:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110



числа 1, 10, 100, 1000, ... можно сохранить в памяти на этапе сборки
потом можно узнавать старшую цифру так:


Код

int ExtractAndRemoveHighestDigit(int &number,int digitIndex)
{
    const int weight=DegreesOfTen[digitIndex];
    int digit=0;
    while(number>=weight)
    {
        ++digit;
        number-=weight;
    }
    return digit;
}


тогда раскладывать число на цифры можно так:
Код

void ExtractAllDigits(int number,int *digits)
{
    for(int digitIndex=9;digitIndex>=0;--digitIndex)
        *digits++=ExtractAndRemoveHighestDigit(number,digitIndex);
]


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


--------------------
qqq
PM WWW   Вверх
Akina
Дата 6.4.2009, 22:48 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454



Цитата(Matrex @  6.4.2009,  22:02 Найти цитируемый пост)
Насчет памяти для конкретно этого приложения не критично, поэтому решение "в лоб" допустимо.

Я вообще-то эти вещи не связывал... как я понял, десятичную цифру надо выделять из байта? тогда можно подготовить 3 статических таблицы (или построить эти таблицы при старте прошивки/приложения) и находить ответ одним XLAT.



--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
Matrex
Дата 7.4.2009, 08:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 96
Регистрация: 31.1.2006

Репутация: нет
Всего: 2



Всем спасибо за советы. Вот нашел в своих старых asm проектах и переделал на Delphi (для наглядности). Реалезация похожа на то что предложил maxim1000:


Код

function TForm1.inttostrr(cx,s:integer):byte;
var al,dx,bx:integer;
    num:array [0..2] of byte;

procedure sub_dec;
label sub_dec2,sub_dec1;
begin
            al:=0;
sub_dec2:   cx:=cx-dx;
            if cx<0 then goto sub_dec1;
            al:=al+1;
            goto sub_dec2;
sub_dec1:   cx:=cx+dx;
            num[bx]:=al;
            bx:=bx+1;
end;

begin
            bx:=0;
            dx:=100;
            sub_dec;
            dx:=10;
            sub_dec;
            dx:=1;
            sub_dec;
            result:=num[s];
end;


Это сообщение отредактировал(а) Matrex - 7.4.2009, 08:45
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0730 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.