首页 > 试题广场 > 计数器
[编程题]计数器

小爱有一个奇怪的计数器。在第一个时刻计数器显示数字3,在接下来的每一个时刻,屏幕上的数字都会减1,直到减到1为止。

接下来,计数器会重置为上一个计数周期初始值的两倍,然后再每一个时刻减1。具体过程如下图所示:

找出规律,并打印出t时刻计数器的值。

输入描述:
输入为时刻t,一个整形数字。0<t<1e12


输出描述:
计数器显示的值。
示例1

输入

4

输出

6
//非迭代版本
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long time = scanner.nextLong();
        long value = 3;
        while(time - value > 0){
            time -= (value);
            value <<= 1;
        }
        value -= time - 1;
        System.out.println(value);
    }
}


编辑于 2019-07-08 19:12:12 回复(0)

可以看到每一组time和value相加的和是一样的,4、10、22、48...,且这些之间的差依次为6、12、24...规律就出来了。

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long t = Long.parseLong(br.readLine());
        long sum = 4L, n = 6L;
        while (t >= sum) {
            sum += n;
            n *= 2;
        }
        System.out.println(sum - t);
    }
}
编辑于 2019-07-31 16:46:17 回复(0)
没观察太多,第一个数是3依次递减,减到0的时候value=value*2就ok啊
发表于 2019-07-29 21:05:20 回复(0)
int main() {   
    long t = 0;  
    cin >> t;     long start =  1;  
    while (start<=t)    
  {        
     start = (start *2 +2);   
  }    
  printf("%ld", start - t);     return 0;
}
主要是找规律吧,每一列开始time值分别1,4(=2*1+2),10=(2*4+2),22=(2*10+2),。。。
找到每一列开头time值,就好办了。
通过循环,找到元素t所在列的下一列开头元素time值为start,注意到其中每一列的value值是从下往上递增,然后start-t 即为t对应是value值。

编辑于 2019-07-27 22:56:17 回复(0)
这个题就是找数学公式,也就是等比数列n项和的公式,然后反推!主要用的就是math相关的
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc= new Scanner(System.in);
long m=sc.nextLong();
double n= Math.ceil(Math.log(m/3.0+1)/Math.log(2));
System.out.println((long)(3*Math.pow(2, n-1)-m+3*(Math.pow(2, n-1)-1)+1));//里面可以合并
}
}


然后发现后面的输出里面可以合并
于是:
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc= new Scanner(System.in);
long m=sc.nextLong();
double n= Math.ceil(Math.log(m/3.0+1)/Math.log(2));
System.out.println((long)(6*Math.pow(2, n-1)-m-2));
}
}
这个算法时间复杂度是O(1),比其他的O(lgn)的要好一些!
编辑于 2019-07-25 10:04:23 回复(0)
#include <iostream>

int main()
{
    long int t,tTemp=1;
    int n=1;
    std::cin >> t;
    while ((t-(((tTemp <<n)-1)*3))>0)
    {
        n++;
    }
    t = t - ((tTemp <<( n-1)) - 1) * 3;
    std::cout << (3*(tTemp <<(n-1)))-t+1<< std::endl;
}
发表于 2019-07-10 10:58:21 回复(0)
套用等比数列公式,O(1)的时间复杂度,python2的代码。
import math
t = int(raw_input().strip())
n = math.ceil((math.log(t/3.0+1,2)))
start = 3*(2**(n-1))
t -= 3*(2**(n-1)-1)
print int(start-t+1)


发表于 2019-08-05 17:11:45 回复(0)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long time = sc.nextLong();
        calDisplayNum(time, 3);
    }
    
    private static void calDisplayNum(long time, long value) {
        long result = time - value;
        if (result <= 0) {
            result = value - time + 1;
            System.out.println(result);
        } else {
            calDisplayNum(time-value, value<<1);
        }
    }
}

发表于 2019-07-06 18:09:53 回复(0)