首页 > 试题广场 > 计数器
[编程题]计数器
  • 热度指数:1548 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

小爱有一个奇怪的计数器。在第一个时刻计数器显示数字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)
#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 回复(0)
#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)
#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)
#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)

可以看到每一组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)
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	long t;
	cin >> t;
	long x = log(1 + float(t) / 3) / log(2);
	long end = 3 * (pow(2, x + 1) - 1);
	cout << (end - t + 1) << endl;
}
等比数列
发表于 2019-09-18 18:10:33 回复(0)
def init(n):
    if n == 1:
        return 1
    else:
        return 2*init(n-1)+2
m = int(input())
n = 1
while(True):
    if m < init(n):
        break
    else:
        n += 1
init_time = init(n-1)
init_value = init_time + 2
result = init_value - (m - init_time)
print(result)
发表于 2019-09-16 14:37:57 回复(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)
n=int(input().strip())
i=1 count=3 k=0 while count<=n: if n<=count+3*(2**(i-1)):
        k = 3*2 ** (i - 1)- n+count+1  count=3*(2**i-1)
    i+=1 print(k)
发表于 2019-09-03 15:17: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)

问题信息

上传者:小小
难度:
16条回答 1525浏览

热门推荐

通过挑战的用户

查看代码