十进制< - >二进制转换算法 [英] the algorithm of decimal<->binary conversion
问题描述
我正在编写一个程序，用于列出相同长度的所有二进制数
，且数量相同的1。
例如
0011
0101
0110
1001
1010
1100
我的算法如下...
0.使用公式计算数字数量
1。温度= 1; outputed = 0;
2.从1到2计算所需长度的功率
2.1将temp转换为char中的二进制数[]
2.1.1临时/ 2得到剩余
2.1.2等等等等等等等等等等of 1s == required no。，output + 1，printf
2.2 temp + 1;
2.3如果输出> =计算出的值，则打破
它完美运行......
但是即使在计算长度为20的二进制数时它看起来也太慢了......
（因为这是一个程序）对于演示在线acm比赛，设定时间限制...）
我怎样才能让它更有效率????
Thx ~~~ 〜
火星。
I''m writing a program for listing all binary numbers of the same length
with the same number of 1s.
e.g.
0011
0101
0110
1001
1010
1100
my algorithm is as follows...
0. use a formula to calculate the number of numbers
1. temp=1; outputed=0;
2. count from 1 to 2 to the power of the required length
2.1 convert temp to a binary number in a char[]
2.1.1 temp/2 get remainder
2.1.2 blah blah blah.........
2.1.2.1 if no. of 1s == required no., output+1, printf
2.2 temp+1;
2.3 if output>=the value calculated, break
it works perfectly...
but it seems too slow even when calculating binary numbers of length 20...
(as this is a program for the demo online acm contest, time limit is set...)
how can I make it more efficient????
Thx~~~~
Mars.
推荐答案
Mars写道：
我正在编写一个程序，用于列出相同长度的所有二进制数
具有相同数量的1。
< snip>
它完美地工作...
但是即使在计算长度为20的二进制数字时它似乎太慢了......
（因为这是一个用于演示在线acm比赛的程序，时间限制已设定......）
我怎样才能让它更有效率????
I''m writing a program for listing all binary numbers of the same length
with the same number of 1s.
<snip>
it works perfectly...
but it seems too slow even when calculating binary numbers of length 20...
(as this is a program for the demo online acm contest, time limit is set...)
how can I make it more efficient????
确保你使用的是高效的算法ithm。
使用分析器来识别主要瓶颈。
重写瓶颈代码。
迭代直到足够快。
Make sure you are using an efficient algorithm.
Use a profiler to identify the principal bottleneck.
Rewrite the bottleneck code.
Iterate until fast enough.
infobahn提到：
infobahn mentioned:
Mars写道：
Mars wrote:
我正在编写一个列出所有二进制数的程序相同长度
相同数量的1。
I''m writing a program for listing all binary numbers of the same length
with the same number of 1s.
< snip>
<snip>
它完美无缺...
但是即使在计算长度为20的二进制数字时它似乎太慢了......
（因为这是一个用于演示在线acm比赛的程序，时间限制已设定......）
如何才能提高效率????
it works perfectly...
but it seems too slow even when calculating binary numbers of length 20...
(as this is a program for the demo online acm contest, time limit is set...)
how can I make it more efficient????
确保使用高效算法。
使用分析器识别主要瓶颈。
重写瓶颈代码。
迭代到足够快。
Make sure you are using an efficient algorithm.
Use a profiler to identify the principal bottleneck.
Rewrite the bottleneck code.
Iterate until fast enough.
ummm ....
这个还不够好吗？
typedef struct
{
char bits [2000];
int pointer;
int length;
}转发;
转换（长输入）
{
int pass;
conv rconv;
rconv = init（）;
while（1）
{
if（（输入！= 1）&&（输入！= 0））
{
pass =输入％2;
输入/ = 2;
}
其他
{
rconv.bits [rconv.pointer] =输入+ 48;
rconv.pointer ++;
if（输入== 1）
rconv.length ++;
休息;
}
if（pass == 1）
{
rconv.bits [rconv.pointer] =''1'';
rconv.pointer ++;
rconv.length ++;
}
其他
{
rconv.bits [rconv.pointer] =''0'';
rconv.pointer ++;
}
}
ummm....
is this good enough??
typedef struct
{
char bits[2000];
int pointer;
int length;
}conv;
conv convert(long long input)
{
int pass;
conv rconv;
rconv=init();
while (1)
{
if ((input!=1)&&(input!=0))
{
pass=input%2;
input/=2;
}
else
{
rconv.bits[rconv.pointer]=input+48;
rconv.pointer++;
if (input==1)
rconv.length++;
break;
}
if (pass==1)
{
rconv.bits[rconv.pointer]=''1'';
rconv.pointer++;
rconv.length++;
}
else
{
rconv.bits[rconv.pointer]=''0'';
rconv.pointer++;
}
}
2005年2月21日星期一01 ：18：35 +0800，火星
< Mars @ M ARS>写道：
On Mon, 21 Feb 2005 01:18:35 +0800, Mars
<Mars@Mars> wrote:
我正在编写一个程序，用于列出相同长度的所有二进制数，并且具有相同数量的1。
这不是主题所说的。
它完美运行......
但是即使在计算二进制数据时看起来也太慢了数字长度20 ...
是的，这是一百万（和一点点）测试。
（因为这是一个演示程序在线acm比赛，设定时间限制...）
啊。可能是因为你想在
比赛中使用别人的工作吗？可能被认为只是一点点不道德的事情？
我怎样才能让它更有效率????
I''m writing a program for listing all binary numbers of the same length
with the same number of 1s.
That''s not what the subject line says.
it works perfectly...
but it seems too slow even when calculating binary numbers of length 20...
Yes, that''s a million (and a bit) tests.
(as this is a program for the demo online acm contest, time limit is set...)
Ah. Might it be that you are looking to use someone else''s work in a
contest? Might that be considered just a tad unethical?
how can I make it more efficient????
将你的算法更改为更多高效的。提示：用比特数代替
指数时间，可以做O（M * N）（其中M
是设置的位数和N是总位数）。实际上
它可以做得更好。想想换班......
Chris C
Change your algorithm to a more efficient one. Hint: instead of an
exponential time with the number of bits, it can be done O(M*N) (where M
is the number of bits set and N is the total number of bits). In fact
it can be done better than that. Think shifts...
Chris C
这篇关于十进制< - >二进制转换算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
