首页 > 试题广场 >

计数器

[编程题]计数器
  • 热度指数：3877 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

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

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

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

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


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

输入

4

输出

6
算法知识视频讲解
添加回答
小蝌蚪666头像 小蝌蚪666 
#include <iostream>
using namespace std;
int main(void){
    //1e12大于int类型范围
    long long t, time = 3;
    cin>>t;
    while(t > time){
        t -= time;
        time *= 2;
    }
    cout<<time+1-t<<endl;
    return 0;
}
变量time表示当前周期的起始计数大小，分别是3,6,12,...，t减去相应的周期大小，当t不大于下一周期大小时，表示在当前周期显示，观察题目所给的表格，发现time+value为定值，为了表示方便，再把time减去上一周期的起始值，得到索引1,2,3,...这些索引值加上value之和等于本周期起始计数值加1
编辑于 2019-08-23 15:59:38 回复(1)
好吃懒做贪玩东头像 好吃懒做贪玩东 
//非迭代版本
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)
Java
谁的电脑头像 谁的电脑

可以看到每一组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)
牛客428994239号头像 牛客428994239号 
t=input('');
x=3; a=3;
while 1
    if t<3
        fprintf('%d',4-t);
        break
    elseif t-a<2*x
        fprintf('%d',2*x-(t-a)+1);
        break
    else
        x=x*2; a=a+x;
    end
end

编辑于 2020-06-03 18:08:06 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;
int main(){
    long t,v=3,k=1;
    cin>>t;
    while(t>=k){
        k += v;
        v<<=1;
    }
    cout<<k-t<<endl;
    return 0;
}

发表于 2019-11-02 08:53:37 回复(0)
C/C++
昔遥暮云头像 昔遥暮云 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int t,velue=3,index=1;
    cin>>t;
    while(index<=t){
        index+=velue;
        velue<<=1;
    }
    cout<<index-t;
    return 0;
}

发表于 2019-10-19 16:49:15 回复(0)
嗦鹅头像 嗦鹅
#######################################################计数器
import math
s = int(input())
#先计算s属于第几个计数器
n = math.ceil(math.log(s/3+1,2))   #要向上取整
#再计算是第几个数
print(3*(2**(n-1)) - s+ 3*(2**(n-1))-2)
发表于 2019-09-13 12:55:21 回复(0)
无心2019头像 无心2019 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long t,n=3,m=1,f=3;
    cin>>t;
    while(m<t)
    {
        m=m+f;
        f=2*f;
    }
    if(m==t)
        cout<<f<<endl;
    else
    {
        f=f/2;
        m=m-f;
        long long res=f-(t-m);
        cout<<res<<endl;
    }
    return 0;
}

发表于 2019-08-21 20:53:35 回复(0)
你男朋友、头像 你男朋友、
没观察太多，第一个数是3依次递减，减到0的时候value=value*2就ok啊
发表于 2019-07-29 21:05:20 回复(0)
dodger头像 dodger 
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)
阿智1头像 阿智1
#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)
Python3
TS9527头像 TS9527
找规律可以得到答案的数学公式。
首先，以这个计数器一次循环作为一组，可以发现对于第i轮循环，这个计数器会跳过的数字的数量是。那么，跳完了第j组的所有数字后，这个计数器总共跳过的数字数量由等比数列求和公式可以得到是。
现在，我们希望求得第t个数的数值，就需要确定第t步所在的组。我们前面已经跳过了k组，那么应有，可以解得。显然，k为一个整数，因此取。这里需要特别注意的是，当为整数的时候，这个解应该减1才能满足小于条件（因为向下取整不会取到比这个整数小）。不过，我们可以发现，当t满足这个情况的时候，计数器的值为1，因此可以直接输出1。
现在我们知道前面跳了k组了，那么计数器在第t时刻就在第组。第组的起始数值为。前面k组已经占用的时刻数，也就是跳过的数量为，因此要跳到第t时刻还要再跳次。跳完这么多次后计数器上显示的数值，也就是答案，为。

AC代码： 
import math


class MainActivity:

    def main(self):
        # Read the data
        t = int(input())
        # Calculate the result
        k = math.log2(t / 3 + 1)
        if math.floor(k) == k:
            print(1)
            return
        k = math.floor(k)
        result = 3 * 2 ** k - (t - 3 * (2 ** k - 1)) + 1
        print(result)


if __name__ == '__main__':
    M = MainActivity()
    M.main()
发表于 2024-09-02 16:23:38 回复(0)
王珍珍是最棒哒头像 王珍珍是最棒哒 
#include<stdio.h>
#include<math.h>
int main()
{
    long long time;
    long long value;
    long long time_init;
    long long low;//hangshu 0kaishi
    scanf("%ld",&time);
    low=(int)(log((time+2)/3)/log(2));
    time_init=3*pow(2,low)-2;
    value=time_init+2-(time-time_init);
    printf("%ld",value);
    
    return 0;
}
找出规律 开头的time是3*2^i-2   value是3*2^i   其中i是行数从0开始的。用输入的时间求出行数，再求输入的时间与这行开头的时间差（time-time_init），再用开头的value减去
发表于 2021-08-19 15:12:24 回复(0)
牛客758087690号头像 牛客758087690号 
t=int(input())
tik=0
base=3
while t>base:
    t=t-base
    tik+=1
    base=2*base
res=base-t+1
print(res)

发表于 2021-03-27 11:01:51 回复(0)
C/C++
牛客549207409号头像 牛客549207409号
#include<iostream>
#include<cmath>
int main()
{
    long long t;
    while(std::cin>>t)
    {
        long double d=(t+3.0)/3.0;
        long long a=log2(d);
        if(pow(2,a)==d)std::cout<<1<<std::endl;
        else
        {
            long long b=t-3*(pow(2,a)-1);
            long long c=3*pow(2,a)-b+1;
            std::cout<<c<<std::endl;
        }

    }
    return 0;
}
发表于 2020-09-18 18:20:27 回复(0)
木子大侠头像 木子大侠 
#include <iostream>
using namespace std;
int main()
{
    unsigned long long a,b,t,r;//足够用的数据类型
    cin>>t;
    a=3,b=3;
    while(t>a)//计算到t出现的周期
    {
        a+=2*b;//左下元素time的规律
        b*=2;//右上元素value规律
    }
    r=a-t+1;//t时刻的计数值
    cout<<r<<endl;
    return 0;
}

编辑于 2020-08-15 20:42:09 回复(0)
努力努力Myzz头像 努力努力Myzz 
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            long n = Long.parseLong(sc.nextLine());
            long i = 0;
            long cur = 0;
            long nextcur = 0;
            while(true){
                cur = 1 * 3 * i + 1;
                nextcur = 1 * 3 * (2*i+1)+1 ;
                if(n<nextcur && n >=cur){
                    break;
                }
                i = 2*i + 1;
            }
            cur -= (n - cur -2);
            System.out.println(cur);
        }
    }
}
不太聪明的解法
发表于 2020-06-30 13:05:19 回复(0)
杜子201902221936389头像 杜子201902221936389
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    long long t;
    cin>>t;
    long long n=0;
    n=(long long)(log((t+3)/3)/log(2)-1);
    long long m=3*(pow(2,n+2)-1);
    cout<<m+1-t<<endl;
    return 0;
}
发表于 2020-06-22 15:29:36 回复(0)
柠檬小精灵头像 柠檬小精灵
t = int(input())

# 判断属于哪一组
n = 1
while(t > (3*pow(2,n) - 3)):
    n = n + 1

s = 3*pow(2,n) - 2
print(s - t)




编辑于 2020-06-15 15:11:09 回复(0)
提交观点

问题信息

C++工程师 穷举 2019 寒武纪 数学 Java工程师
来自：寒武纪2019秋招软件...
上传者：小小
难度：
29条回答 9716浏览

热门推荐

通过挑战的用户

查看代码

相关试题

计数器

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号