Question

编写一个算法，对于输入的十进制非负整数，将它的二进制表示打印出来。

Answer 1

【答案】：(1)数据结构
采用栈的顺序表示定义。
(2)思路
将输入的十进制数字反复除以2，直到商为0。将每次的数字模2的余数入栈。栈中存放的就是所要求的二进制表示。再将栈中的元素依次弹出打印即可。
(3)算法
void print_bin(int dec_number){
/*将十进制非负整数转化为二进制数打印出来*/
PSeqStack pastack;
int temp=dec_number;
if(temp＜0){
printf("Error!\n");
return;
}
pastack=createEmptyStack_seq(); /*建立一个空栈*/
if(pastack==NULL)return;
while(temp＞0){
push seq(pastack,temp%2);
temp/=2;
}
while(!isEmptyStack_seq(pastack)){
printf("%d",top_seq(pastack));
pop_seq(pastack);
}
free(pastack);
}
(4)代价分析
设输入的十进制数字为n，则算法的时间代价为O(log₂n)。空间代价主要是栈的大小，为O(log₂n)。