Алгоритм разбивания числа на разряды

[FallenSoul]

Приветы.

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

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


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

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

3) Что-то ещё можно придумать, более простое?

[Finch]

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

[FallenSoul]

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

Изначально у меня число int, но для вывода перевожу в строку и методом

Код:

m_StaticSumma.SetWindowText(buf);

вывожу

[Finch]

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

[FallenSoul]

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

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

[Finch]

Для 32 разрядных машин int может принимать значения от -2147483648 и до 2147483647. Кстати твое число все равно не входит в эти рамки. Надо наверно применять long int

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

Это всецело зависит от выбранного метода. В большинстве случаев метод insert отодвигает уже сушествуюшие символы и вставляет между ними.

[Алексей++]

Код:

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;
}

[Вад]

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

[npak]

Вот решение для 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;
}

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

[Антон (LogRus)]

я вот чего натворил

Код:

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]

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

Код:

#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>

что и требовалось...

[Вад]

Код:

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

Имхо, вариант с функтором как-то посимпатичнее, нежели публичная строка в классе

[aguest2007]

Вот попробовал причесать

Код:

#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();
}