Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Деление меньшего на большее


Автор: GIK 28.12.2007, 10:12
Всем доброго времени суток.
Народ, кто знает как реализовать побитово деление меньшего числа на большее?
ОЧЕНЬ НАДО.

Автор: maxim1000 28.12.2007, 11:16
и что должно получиться в результате?
(т.е. в каком формате)

Автор: Akina 28.12.2007, 11:20
Тупо ноль и меньшее в остатке. smile 

Автор: GIK 28.12.2007, 11:23
Я написал алгоритм деления больших чисел, нереально больших, до 1000 символов, правда там еще учесть кое что надо, вот он:
Код

#include <stdio.h>
#include<iostream.h>
#include<conio.h>

#include<math.h>


void main()
{ char a[1000]={0};
  char b[1000]={0};
  char buf[1000]={0};

  int len_a=0, len_b=0;

  printf("%s", "Vvedite chislo 1: ");
  scanf("%s", &a);
  for(int i=0; a[i]; i++){len_a++;}
  printf("%s", "\n chislo 1 imeet dlinu: ");
  printf("%d", len_a);
  printf("%s", "\n Vvedite chislo 2: ");
  scanf("%s", &b);
  for(int i=0; b[i]; i++){len_b++;}
  printf("%s", "\n chislo 2 imeet dlinu: ");
  printf("%d", len_b);
  if(len_a>len_b) {printf("%s", "\n chislo 1 bolshe chisla 2, delimoe chislo 1:");}
  else if(len_a<len_b){printf("%s", "\n chislo 2 bolshe chisla 1, delimoe chislo 2:");
   for(int i=0; i<len_b; i++)
    {
     buf[i]=b[i];
     if(a[i]) //esli tam choto est
         {b[i]=a[i];a[i]=buf[i];}
     else{ //ïðåêðàùàåì çàïîíÿòü b[], íà÷èíàåì îáíóëÿòü åãî
           b[i]=0;
           a[i]=buf[i];
         }
    }
  printf("%s", "\n teper chislo a =");
  for(int i=0; a[i]; i++)
  printf("%c", a[i]);
  printf("%s", "\n a chislo b =");
  for(int i=0; b[i]; i++)
  printf("%c", b[i]);
  }else  //Äëèíû ðàâíû
  {  bool aBOLSHEb=false;
    for(int i=0; i<len_a; i++)
     {
       if( (a[i]-48) > (b[i]-48) )
        { aBOLSHEb=true; break;} //chislo a > b
        else if( (a[i]-48) == (b[i]-48) )
          continue;
        else if((a[i]-48) < (b[i]-48) )
          {aBOLSHEb=false; break;}
     }
    if(!aBOLSHEb)
    {
     for(int i=0; i<len_a; i++)
      {
        buf[i]=a[i];
        a[i]=b[i];
        b[i]=buf[i];
      }
     printf("%s", "\n teper chislo a =");
     for(int i=0; a[i]; i++)
     printf("%c", a[i]);
     printf("%s", "\n a chislo b =");
     for(int i=0; b[i]; i++)
     printf("%c", b[i]);
    }
  }
  int ITOG=0;
  int ranINT_a=0, ranINT_b=0, ran_ab=0;
  char ranCHAR_a=0, ranCHAR_b=0;

  bool ee=true;
  int p=0; //ýëëåìåíò óìåíüøàþùèé ÷èñëî
while(ee)
{
  for(int i=(len_b-1); i!=-1 ; i--) //ïî ìåíüøåìó ÷èñëó
  {
    if( (a[i]-48) > (b[i]-48) ) //Âïåðåäè (ò.å. ñëåâà) èçìåíåíèé íå ïðîèçîéäåò :)
     {
       ranINT_a =(a[i]-48);
       ranINT_b=(b[i]-48);
       ran_ab=ranINT_a-ranINT_b;
       a[i]= (ran_ab +48);
       //a[i]=ranCHAR_a;

     }else
     if( (a[i]-48) == (b[i]-48) ) //Ò.å. âïåðåäè (ò.å. ñëåâà) èçìåíåíèé íå ïðîèçîéäåò :)
     {
       a[i]='0';
     }
     else //Åñëè ÷èñëî ìåíüøå, îáðàùàåìñÿ ê áèòàì ñëåâà
     {
       if( (a[i-1] - 48)!=0 ) //Åñëè ñëåâà íå 0
        {
         ranINT_a=0; //Îáíóëÿåì
         ranINT_a= (a[i-1] - 48);
         ranINT_a--;
         a[i-1] = (ranINT_a +48) ;
         //Ó÷èòûâàåì ðàçíèöó ìåæäó ÷èñëàìè
         ranINT_a = (a[i] - 48);
         ranINT_b= (b[i]-48);
         ranINT_a = (10+ranINT_a) - ranINT_b;

         a[i] = (ranINT_a+48);

        }
        else
        { int er=0;
          while(a[i-(er+1)]=='0')
          { er++;
          }

          ranINT_b= (b[i]-48);
          a[i]=  (10 - ranINT_b)-48; //ñèìâîë èç a[i] ïàðàëåëüíûé b[i], êîòîðûé áûë =0, ìåíÿåòñÿ íà 10 - b[i], âñå îñòàëüíûå, ïðåäñòîÿùèå, òîæå ìåíÿþòñÿ

         //âñå ñèìâîëû ñ ÍÓËßÌÈ, äî ñèìâîëà a[i], ìåíÿþòñÿ íà 9
         //è ñàìûé êðàéíèé îòëè÷íûé îò íóëÿ óìåíüøàåòñÿ íà 1
          for(int nn=1; nn<=er; nn++)
           a[i-nn]='9';
          //è ïåðâûé ïîñëå íóëåé
          ranINT_a = a[i-(er+1)]-48;
          ranINT_a--;
          a[i-(er+1)]= (ranINT_a+48);

        }

     }

  }

  if(a[p]=='0') //Êðàéíåå çíà÷åíèå = 0, ïåðåìåùàåì ìàññèâ
  {
    p++; //÷èñëî óìåíüøèëîñü
    len_a--; //Äëèíà óìåíüøèëàñü
    for(int j=0; j<len_a; j++)
    {
     a[j]=a[j+1];

    }
    a[len_a - 1] = 0;
  }
  if(len_a==len_b)
  {
     if( (a[(len_a - len_b )]-48) < (b[0]-48))
     ee=false;
   }else if(len_a < len_b)
    ee=false; 
 ITOG++;

}
  printf("%s", "\n Itog delenia = ");
  printf("%d", ITOG);

  printf("%s", "\n chislo a=");
  for(int i=0; a[i]; i++)
     printf("%c", a[i]);



 getch();

};


А мне нужно знать ка разделить например 2/7, и вывести хотябы 2 символа после запятой, люди помогите пожалуста еще 3 часа осталось :(

Добавлено через 9 минут и 39 секунд
Цитата

и что должно получиться в результате?

В любом, хоть что нибудь, все пойдет

Автор: maxim1000 28.12.2007, 11:57
Цитата(Akina @  28.12.2007,  11:20 Найти цитируемый пост)
Тупо ноль и меньшее в остатке.

ну необязательно же нацело smile

я потом и спросил формат, что задание предполагает дробное число

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

выбор множителя зависит от нескольких условий:
1. нужно, чтобы умноженное число не вылезло из диапазона ячейки, в которой его собираются хранить, т.е. если у нас числа 0<=x<1 и хранить будем в байте, вполне подойдёт множитель 256
2. если известно, что числа будут не больше какого-то максимума, то множитель стоит брать наибольший из возможных, чтобы получить наилучшую точность
3. [это, скорее, специфично для данной задачи] простота: если уж хочется просто выводить число в 10-й системе, то можно взять множитель 10^n, соответственно, можно будет хранить n знаков после запятой и выводить их

Автор: Akina 28.12.2007, 13:12
Цитата(GIK @  28.12.2007,  12:23 Найти цитируемый пост)
разделить например 2/7, и вывести хотябы 2 символа после запятой

2/7 = ((2 shl 8)/7) shr 8

Автор: GIK 3.1.2008, 12:33
Чет не догоняю вообще ребят, ваши советы smile из меня наверно хреновый математик...
Мне тут по пьяне пришла в голову вот такая мысль: По сути когда делим меньшее число на большее, это  есть деление КАЖДОЙ ЕДЕНИЦЫ из меньшего числа умноженное на количество этих едениц, т.е. само число. Пример 7/26 это 1/26, 7 раз Я не могу хранить (или не умею) дроби, зато я могу хранить целы числа! А как мне это сделать? Оказывается очень просто- вместо 1-цы ставим 100 (в данном случае, т.к. делитель 26) в результате 100/26 = 3,84 (округляем) = 3. Теперь умножаем на 7 = 21.
Проверим на калькуляторе 7/26 = 0,26 а у нас 21 - разница большая... Значит надо как то уменьшить погрешность. Разделтим теперь 10000 / 26 = 384,61 = 384 *7 =  2688 
Сравниваем 7/26=0,2692, а у нас 2688. Видим что это вариант имеет меньшую погрешность. 
На данный момент это мне подходит т.к. для моей задачи мне достаточно знать 2 знака после запятой.
Но конечно хотелось бы знать как считает калькулятор smile  

Автор: maxim1000 3.1.2008, 12:51
но ведь гораздо проще взять 700/26 и поставить запятую, где надо smile

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)