title: K-进制数
date: 2018-12-27 09:21:00
author: LHL
img: https://img-blog.csdnimg.cn/2018122214540225.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTIzNjIy,size_16,color_FFFFFF,t_70
top: false
cover: true
coverImg: https://img-blog.csdnimg.cn/2018122214540225.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTIzNjIy,size_16,color_FFFFFF,t_70
toc: true
mathjax: false
categories: 程序设计
tags:

  • c语言
  • ACM

K-进制数

题目描述

考虑包含N位数字的K-进制数. 定义一个数有效, 如果其K-进制表示不包含两连续的0.

考虑包含N位数字的K-进制数. 定义一个数有效, 如果其K-进制表示不包含两连续的0. 例: 1010230 是有效的7位数 1000198 无效 0001235 不是7位数, 而是4位数. 给定两个数N和K, 要求计算包含N位数字的有效K-进制数的总数. 假设2 <= K <= 10; 2 <= N; 4 <= N+K <= 18.

输入

两个十进制整数N和K

2

10

输出

十进制表示的结果

90

样例输入

样例输出

根据题意,要知道 N 位K 进制并且 不能有连续两个0出现 还有首位不能为0 的限制条件。

本着由简到难的思想 :

​ 假设是让你求 1位 K 进制的满足条件的数,那么满足条件的数则有 1,2,3…..K-1 一共K-1个数对吧,

我们记作 res_1=K-1,那么不满足条件的数 只有 0 ,一共1个数 ,我们记作res_0=1。

​ 假设是让你求 2位 K 进制的满足条件的数,那么先考虑首位(也就是第2位),可以填的数为除去0的其他数,

有 1,2,3…..K-1 一共K-1个数对吧,而这第二位可以填的数 可以和第一位的所有数搭配,

以1为例,有 11,12,13,…..1(K-1),还有在第一位不满足条件的 0 搭配 10,也是满足条件的数,

所以2位K进制满足条件的数res_1=(K-1)(K-1+1),即 res_1=(K-1)(res_1+res_0),对吧,

再来看不满足条件的数 即 首位为0的 有 01,02,03…..0(K-1),一共有K-1个也就是res_0=K-1,即 res_0=res_1(上一个)。

第一位满足条件的数res_1对吧,因为不能连0 ,虽然00也是不满足,但是 00这种情况是绝对不满足,

而首位不满足的情况是相对不满足,绝对和相对 懂吧。

​ 那么继续,假设是让你求 3位 K 进制的满足条件的数,同样先考虑首位(也就是第3位),

可以填的数为除去0的其他数,有 1,2,3…..K-1 一共K-1个数对吧,而这第3位可以填的数

可以和2位K进制满足条件和(相对)不满足条件的数搭配,即 res_1=(K-1)[(K-1)(K-1+1)+(K-1)],

即 res_1=(K-1)*(res_1+res_0),不满足条件的数则是可以和2位K进制满足条件的数搭配,

res_0=(k-1)*(K-1+1),即res_0=res_1。

后面的位数就以此类推,再看看图解。

img

AC代码:

#include<stdio.h>
int main()
{
  int N,K,i,res_0,res_1;//res_1代表最高位非0  res_0代表最高位为0的结果 
  while(scanf("%d%d",&N,&K)!=EOF){
      res_1=K-1,res_0=1;//如果只有一位时 K进制首位为1的可以填的为K-1个数去掉为0 
      for(i=2;i<=N;i++){ 
      int last_res_1=res_1;//暂存 
      res_1=(K-1)*(res_1+res_0);//如果高位为1 则结果为上一次结果为1和为0的数的个数 
      res_0=last_res_1; //如果高位为0 则结果为上一次结果为1的数的个数 
      }
      printf("%d\n",res_1);
   }
    return 0;
}

  转载请注明: Five-great的博客

 本篇
title: K-进制数date: 2018-12-27 09:21:00author: LHLimg: https://img-blog.csdnimg.cn/2018122214540225.png?x-oss-process=ima
2019-03-02 LHL
下一篇 
Hello World Hello World
Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hex
2019-03-02 LHL