Chinaunix首页 | 论坛 | 博客
  • 博客访问: 671453
  • 博文数量: 141
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1114
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-17 14:32
个人简介

小公司研发总监,即当司令也当兵!

文章分类

全部博文(141)

分类: LINUX

2017-06-05 23:39:34

题目描述

给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是:

1,3,4,9,10,12,13,…

(该序列实际上就是:3^0,3^1,3^0+3^1,3^2,3^0+3^2,3^1+3^2,

3^0+3^1+3^2,…)

请你求出这个序列的第N项的值(用10进制数表示)。


分析:
对于任意阶n, 由k的n阶(小于n阶)次幂组成的序列为:
0*k^n + 0*k^(n-1)+...+1*k^0 ,  0*k^n + 0*k^(n-1) + ...+ 1*k^1 + 0* k^0 , ..., 1*k^n + 1*k^(n-1) + ... + 1* k^0

上面是一个二项式的完全表达式, 对于n,每个项由(n+1)个系数项组成:bit表示为[b0...1, b1...1], 共2^(n+1) -1 项
对于序列的第N项,如果N表示为(p1*2^0 + p2*2^1+ ...pt*2^(t-1) )
那么序列的第N项的值表示为 p1*k^0 + p2*k^1 + ... pt*k^(t-1)

实现:

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <math.h>


  5. unsigned long seriesN (unsigned int key, unsigned int N)
  6. {
  7.     unsigned long sc = 1;
  8.     unsigned long ret = 0;

  9.     while (N > 0)
  10.     {
  11.         ret += (N & 0x01) > 0 ? sc : 0;
  12.         sc *= key;
  13.         N = N >> 1
  14.     }

  15.     return ret;
  16. }

阅读(1980) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~