Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Алгоритм разбивания числа на разряды  (Прочитано 17397 раз)
0 Пользователей и 1 Гость смотрят эту тему.
FallenSoul
Опытный

ru
Offline Offline
Пол: Мужской

« : 15-07-2008 20:45 » 

Приветы.

Такой вопрос, вроде бы простой, но запутался в нём.

Имеем число: 6128329324.
Задача: Преобразовать его к виду 6.128.329.324.


1) Можно сделать какой-то сумасшедший цикл, в котором обход с конца до начала делать, и каждый 4й символ помечать ".", а цифру этого 4го символа тащить через весь цикл, попутно устраивая переприсваивание.

2) Можно сделать несколько массивов, длинной в 3 символа, и пустить цикл на разбивку числа по 3 цифры в каждый массив, а затем через соединение строк преобразовать вновь к единому. Проблема в том, чтоб организовать 1 цикл на, допустим, все 5 массивов. Тогда придётся работать с динамически выделенной памятью, и переходить к следующему массиву через указатели, не используя имён.

3) Что-то ещё можно придумать, более простое?
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #1 : 15-07-2008 20:48 » 

FallenSoul, А как ты вообше храниш число? В виде строки или как числовая переменная.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
FallenSoul
Опытный

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 15-07-2008 20:50 » 

Ну я думаю из одного, можно сделать без труда второе?

Изначально у меня число int, но для вывода перевожу в строку и методом
Код:
m_StaticSumma.SetWindowText(buf);
вывожу
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #3 : 15-07-2008 20:53 » 

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

Не будите спашяго дракона.
             Джаффар (Коша)
FallenSoul
Опытный

ru
Offline Offline
Пол: Мужской

« Ответ #4 : 15-07-2008 20:55 » 

Наверняка поверх уже существующего =\

Я тут немного задумался. Как у меня int может принимать 600 миллиардов, если на лекциях нас уверяли что его промежуток -32768, +32768. Или это только в Borland 3.1 и дело в 32 битном представлении?
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #5 : 15-07-2008 21:07 » 

Для 32 разрядных машин int может принимать значения от -2147483648 и до 2147483647. Кстати твое число все равно не входит в эти рамки. Надо наверно применять long int Улыбаюсь
Цитата
Наверняка поверх уже существующего =\
Это всецело зависит от выбранного метода. В большинстве случаев метод insert отодвигает уже сушествуюшие символы и вставляет между ними.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #6 : 16-07-2008 03:43 » 

Код:
const char* pchScr="12345678";
char* pchDst=0;

int NumsOnPoint=3;
int srclen=strlen(pchScr);
if(srclen)
{
DWORD dwdPointsNum=(srclen-1)/NumsOnPoint;

int newlen=srclen+dwdPointsNum;

pchDst=new char[newlen];

DWORD dwd=0;
const char* pS=pchScr+srclen-NumsOnPoint;
char* pD=pchDst+newlen-NumsOnPoint;

for(dwd=0;dwd<dwdPointsNum;dwd++)
{
memmove(pD,pS,NumsOnPoint);
pD--;
*(pD)='.';

pD-=NumsOnPoint;
pS-=NumsOnPoint;
}

memmove(pchDst,pchScr,srclen%NumsOnPoint);


//pchDst - результат


delete [] pchDst;
pchDst=0;
}
« Последнее редактирование: 16-07-2008 03:45 от Алексей1153++ » Записан

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #7 : 16-07-2008 04:40 » 

Если уж всё равно память двигать - то не проще, скажем, организовать циклическую вставку в std::string в нужные позиции? Число разрядов ведь посчитать труда не представляет, вычислить позиции для вставки, соответственно, тоже, а цикл вставки выглядит куда проще, да и безопаснее...
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #8 : 16-07-2008 21:00 » 

Вот решение для gcc -  сбрасывает в заданный поток разбиение числа на разряды. В примере используется std::cout, для вывода результата в строку достаточно передать std::ostrstream.

программа "заточена" для 64-битных целых.

Код:
#include <iostream>

// Разделитель. В данном случае разделитель точка.
const char DELIMITER = '.';
// Максимальная число цифр в числе. Достигается на 64-битных беззнаковых целых
// (unsigned long long int в gcc и unsigned __int64 в MS VC) порядка 10**19.
const int LONG_LONG_DIGIT_NUMBER = 20;
// Максимальное число знаков в выводе
const int MAX_STRING_LENGTH = LONG_LONG_DIGIT_NUMBER
        + (LONG_LONG_DIGIT_NUMBER/3) // количество разделителей
        + 1 // для знака
        ;


std::ostream& dump_integer(long long number, std::ostream & out) {
        char string[MAX_STRING_LENGTH+1];
        int sign = (number < 0) ? -1 : 0;
        if (sign) { number = -number; }
        if (0 == number) {
                out << "0";
                return out;
        }
        int count = 0;
        int position = MAX_STRING_LENGTH+1;
        string[position] = '\0';
        while (number > 0) {
                long long next_number = number / 10;
                char digit = number - next_number*10;
                if (0 == count % 3) {
                         string[--position] = DELIMITER;
                }
                string[--position] = digit + '0';
                count ++;
                number = next_number;
        }
        if (sign) { string[--position] = '-'; }
        string[MAX_STRING_LENGTH] = '\0';
        return out << string+position;
}

int main() {
        dump_integer(0, std::cout) << std::endl;
        dump_integer(10, std::cout) << std::endl;
        dump_integer(100, std::cout) << std::endl;
        dump_integer(1000, std::cout) << std::endl;
        dump_integer(6128329324LL, std::cout) << std::endl;
        // Большое положительное число
        dump_integer(0x7fffffffffffffffLL, std::cout) << std::endl;
        dump_integer(-10, std::cout) << std::endl;
        dump_integer(-100, std::cout) << std::endl;
        dump_integer(-1000, std::cout) << std::endl;
        dump_integer(-6128329324LL, std::cout) << std::endl;
        // "Большое" отрицательное число
        dump_integer(0x8000000000000001LL, std::cout) << std::endl;
        return 0;
}

Проверка внимательности - в этой программе есть как минимум одна ошибка.
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #9 : 17-07-2008 06:24 » 

я вот чего натворил
Код:
class myfunctor1
{
std::string & s_;
long pos_;
long numsPerPoint_;
public:
myfunctor1(std::string &s, long npp) : s_(s), pos_(0), numsPerPoint_(npp) {}
template<typename T>
void operator()(T c)
{
++pos_;
if (pos_ > numsPerPoint_ && c != '-')
{
pos_ = 1;
s_ = "." + s_;
}
s_ = c + s_;
}
};


class myfunctor2
{
std::string & s_;
long pos_;
long numsPerPoint_;
public:
myfunctor2(std::string &s, long npp, long skip)
: s_(s)
, pos_(skip ? skip : npp)
, numsPerPoint_(npp) {}
template<typename T>
void operator()(T c)
{
if (pos_ == 0)
{
pos_ = numsPerPoint_;
s_ += ".";
}
s_ += c;
--pos_;
}
};

const long step = 2;

void convert1(long long v, std::string & result)
{
std::ostringstream str;
str << v;
std::string s = str.str();
for_each(s.rbegin(), s.rend(), myfunctor1(result, step));
}

void convert2(long long v, std::string & result)
{
std::ostringstream str;
str << v;
std::string s = str.str();
long correct = (v < 0 ? 1 : 0);
long skip = (s.size() - correct) % step;
skip = skip ? skip : step;
skip += correct;
for_each(s.begin(), s.end(), myfunctor2(result, step, skip));
}

void convert3(long long v, std::string & result)
{
char str[40] = {0};
_snprintf(str, sizeof(str) - 1, "%I64d", v);

long len = strlen(str);
const char * c = str + len;
myfunctor1 f(result, step);
do
{
--c;
f(*c);
} while(c != str);
}

void convert4(long long v, std::string & result)
{
char str[40] = {0};
_snprintf(str, sizeof(str) - 1, "%I64d", v);

long len = strlen(str);

long correct = (v < 0 ? 1 : 0);
long skip = (len - correct) % step;
skip = skip ? skip : step;
skip += correct;

const char * c = str + len;
myfunctor2 f(result, step, skip);
for (const char * c = str; str + len != c; ++c)
{
f(*c);
}
}

void test(long long v)
{
{
std::string s;
convert1(v, s);
std::cout << s << std::endl;
}

{
std::string s;
convert2(v, s);
std::cout << s << std::endl;
}

{
std::string s;
convert3(v, s);
std::cout << s << std::endl;
}

{
std::string s;
convert4(v, s);
std::cout << s << std::endl;
}
}

typedef void (*funcpointer)(long long, std::string &);

void perf_test(const std::string & name, funcpointer f)
{
long n = 1000000;
std::cout << "Start test " << name << std::endl;
std::string s;
unsigned long beginTime = GetTickCount();
for (long i = 0; i != n; ++i)
{
s.clear();
f(-123456L, s);
}
unsigned long endTime = GetTickCount();
std::cout << "Done: " << n << " calls " << endTime - beginTime << " ms" << std::endl;

}

int _tmain(int argc, _TCHAR* argv[])
{
test(1);
test(-1);
test(12);
test(-12);
test(123);
test(-123);
test(1234);
test(-1234);
test(12345);
test(-12345);
test(123456);
test(-123456);

perf_test("reverse + stringstream",convert1);
perf_test("forward + stringstream",convert2);
perf_test("reverse + printf",convert3);
perf_test("forward + printf",convert4);

return 0;
}

результаты испытаний(без оптимизации /Od):
Код:
Start test reverse + stringstream
Done: 1000000 calls 13593 ms
Start test forward + stringstream
Done: 1000000 calls 6922 ms
Start test reverse + printf
Done: 1000000 calls 7828 ms
Start test forward + printf
Done: 1000000 calls 2188 ms

результаты испытаний(c оптимизации /O2):
Код:
Start test reverse + stringstream
Done: 1000000 calls 4734 ms
Start test forward + stringstream
Done: 1000000 calls 3344 ms
Start test reverse + printf
Done: 1000000 calls 2594 ms
Start test forward + printf
Done: 1000000 calls 1391 ms
Записан

Странно всё это....
aguest2007
Гость
« Ответ #10 : 19-11-2008 18:45 » 

Попробуй такой рекурсивный вариант алгоритма:

Код:
#include "stdafx.h"
#include <iostream.h>
#include <conio.h>
#include <string>


class hello
{
public:
hello(__int64);
std::string str;
private:
void form(unsigned __int64);
int c;
};

hello::hello(__int64 v)
{
c=0;
if(v<0)
str+="-",v=-v;
form(v);
}

void hello::form(unsigned __int64 v)
{
if(!v)
{
c--;
return;
}
c++;
form(v/10);
str=str+(char)(v%10+'0');
if(!(c%3)&&c)
str=str+'.';
c--;
}


void main(void)
{
hello c(6128329324);
cout<<"<"<<c.str.c_str()<<">";
cout<<endl;
getch();
}

Прога выведет


<6.128.329.324>

что и требовалось...
Записан
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #11 : 20-11-2008 08:53 » 

Код:
class hello
{
public:
hello(__int64);
std::string str;
private:
void form(unsigned __int64);
int c;
};
Имхо, вариант с функтором как-то посимпатичнее, нежели публичная строка в классе Ага
Записан
aguest2007
Гость
« Ответ #12 : 20-11-2008 21:54 » new

Вот попробовал причесать Улыбаюсь
Код:
#include "stdafx.h"
#include <iostream.h>
#include <conio.h>
#include <string>

template<class T> class DelimiterPlace
{
public:
DelimiterPlace(T v,int _step=3,char _del='.'): step(_step), del(_del), c(0)
{
if(v<0)
str+="-",v=-v;
StrForm(v);
}
operator const std::string&() { return str; }
operator const char*() { return str.c_str(); }
private:
void StrForm(T v)
{
if(!v) { c--; return; }
c++;
StrForm(v/10);
str=str+(char)(v%10+'0');
if(!(c%step)&&c)
str=str+del;
c--;
}
int c,step;
char del;
std::string str;
};

void main(void)
{
cout<<"<"<<DelimiterPlace<unsigned __int64>(6128329324)<<">";
cout<<endl;
getch();
}
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines