Java教程

贪心算法实现十进制数转换成二进制八进制十六进制

本文主要是介绍贪心算法实现十进制数转换成二进制八进制十六进制,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

进制转换的原理:

  1. 先将一个十进制数转换成二进制数;
    (构造一个0 ~2^30的数组,用number和数组中每个元素逆序比大小, 如果number >= quan_arr[i], 就让number -= quan_arr[i]; 并且该位置的数就置为1,否则该位置的数置为0, 直到number减为0);
  2. 对quan_arr数组进行不同进制的处理,贪心算法
    贪心算法的思想,从局部最优到整体最优;
    例如八进制:3位可以表示一个数,从数组的0下标开始,依次往后取三位计算出值存入一个临时数组中,所有的二进制位计算完毕后, 将临时数组的值输出即可;
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <math.h>
#define MAX_VALUE 2147483648

void two(int* arr, int high);
void eight(int* arr, int high);
void sixteen(int* arr, int high);


void two(int* arr, int high)
{
	if(arr == NULL || high < 0)
		return;
	printf("二进制:");
	for(int i = high; i >=0; i--)
	{
		printf("%d",arr[i]);
	}
	printf("\n");
}
void eight(int* arr, int high)
{
	if(arr == NULL || high < 0)
		return;
	printf("八进制:");
	int sum = 0;
	int count = high / 3 + 1;
	int j = 0;
	int* tmp =(int*)malloc(sizeof(int) * count);
	if(tmp == NULL) return;
	memset(tmp, 0, sizeof(int) * count);

	for(int i = 0; i <= high; i++)
	{
		sum += pow(2.0, i % 3) * arr[i];
		if((i + 1) % 3 == 0 || i == high)
		{
			tmp[j++] = sum;
			sum = 0;
		}
	}
	for(int i = count; i >= 0; i--)
	{
		printf("%d", tmp[i]);
	}
	printf("\n");
	free(tmp);
	tmp = NULL;
}

void sixteen(int* arr, int high)
{
	if(arr == NULL || high < 0)
		return;
	printf("十六进制:");
	int sum = 0;
	int count = high / 4 + 1;
	int j = 0;
	int* tmp =(int*)malloc(sizeof(int) * count);
	if(tmp == NULL) return;
	memset(tmp, 0, sizeof(int) * count);

	for(int i = 0; i <= high; i++)
	{
		sum += pow(2.0, i % 4) * arr[i];
		if((i + 1) % 4 == 0 || i == high)
		{
			tmp[j++] = sum;
			sum = 0;
		}
	}
	for(int i = count; i >= 0; i--)
	{
		printf("%x", tmp[i]);
	}
	printf("\n");
	free(tmp);
}
//贪心算法实现进制的转换
int calculate(int num)
{
	if(num < 0 || num > MAX_VALUE)
		return -1;
	int* quan_arr = (unsigned int*)malloc(sizeof(unsigned int) * 31);
	if(quan_arr == NULL) return -1;
	memset(quan_arr, 0, sizeof(int) * 31);
	for(int i = 0; i < 31; i++)
	{
		quan_arr[i] = (unsigned int)pow(2.0, (double)i);
	}
		//val   1 2 4 8 16 32...10737411824
		//index 0 1 2 3 4  5 ...30           
	for(int i = 30; i >=0; i--)
	{
		if(num >= quan_arr[i])
		{
			num -= quan_arr[i];
			//将最高位制成1
			quan_arr[i] = 1;
		}
		else
		{
			//不否和的0
			quan_arr[i] = 0;
		}
	}
		//得到quan_arr
		//val 	:0 0 0 1 0 0 ... 二进制
		//index	:0 1 2 3 4 5 6	...	下标
		
		//处理多余的0
	int count = 0;
	for(int i = 30; i >= 0; i--)
	{
		if(quan_arr[i] == 0)
		{
			continue;
		}
		count = i;
		break;
	}
		//count下标对应的数字是第一个1是最高位
	two(quan_arr, count);
	eight(quan_arr, count);
	sixteen(quan_arr, count);

	free(quan_arr);
	quan_arr = NULL;
	return 0;

}
int main()
{
	int num = 0;
	while(1)
	{
		printf("请输入一个十进制数(退出-1):\n");
		scanf("%d",&num);
		if(num == -1)
			break;
		calculate(num);
	}
	return 0;
}

结果:
在这里插入图片描述

这篇关于贪心算法实现十进制数转换成二进制八进制十六进制的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!