我的有道第二题(不是双倍超立方)

简介: 先说明一下,我遇到的第二题跟大家先前讨论的第二题题目不同,不过最近算法挺火,也就放上来,大家一起讨论讨论,而且我觉得有道这次比赛非常好,我看了下TopCode平台,大家平时也可以进这个平台练习一下算法,不过。

先说明一下,我遇到的第二题跟大家先前讨论的第二题题目不同,不过最近算法挺火,也就放上来,大家一起讨论讨论,而且我觉得有道这次比赛非常好,我看了下TopCode平台,大家平时也可以进这个平台练习一下算法,不过。。。。有道的翻译还真有待提高了

 

声明一下,我算法没有学过,只是想到了解决的方法,当时理解题目花了我很多时间,不知道是我太笨还是题目真有问题,呵呵。废话不说,上题目:

Problem Statement

      

一个二进制序列由下面的伪代码生成:

string A = "0"

While (A的长度小于等于n)

    创建一个和A一样长度的字符串B

    For i=0,1,...length(A)-1

        If (i 是完全平方数)

            B[i] = 1-A[i]

        Else

            B[i] = A[i]

    A = A + B (即将B拼接在A后面)

End While

Return A

请注意,在上面的伪代码中,A[i]B[i]分别表示字符串AB中下标为i的字符(下标编号从0开始)。对"完全平方数"的定义是,对于整数i,存在整数j,使得i= j *j,则称i为完全平方数。

下面具体说明序列生成的过程:如果n=7,则在每一轮迭代中,A的取值依次为:0, 01, 0110, 01101010,所以最终产生的二进制序列就是0,1,1,0,1,0,1,0

请返回上述序列中下标为n的数字(该序列的下标从0开始)

Definition

      

Class:

BinarySequence

Method:

getValue

Parameters:

int

Returns:

int

Method signature:

int getValue(int n)

(be sure your method is public)

      

 

Constraints

-

n 的取值大于等于0,小于等于2,000,000,000

Examples

0)

 

      

7

Returns: 0

原因参见题目描述。

1)

2

Returns: 1

2)      

8

Returns: 1

这一次,生成的序列为0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0.

3)      

11

Returns: 0

4)       

10

Returns: 1  

5)      

15

Returns: 0

 

头大,乱七八糟一堆东西,看了老半天,最后跟大家一样,来了句,原来如此啊,ok,理解了题目,上代码:

 

 1 public   class  BinarySequence
 2 img_405b18b4b6584ae338e0f6ecaf736533.gifimg_1c53668bcee393edac0d7b3b3daff1ae.gif     {
 3        public int getValue(int n)
 4img_2887d91d0594ef8793c1db92b8a1d545.gifimg_7a2b9a960ee9a98bfd25d306d55009f8.gif        {
 5            int result = 0;
 6
 7            string A = "0";
 8
 9            while (A.Length <= n)
10img_2887d91d0594ef8793c1db92b8a1d545.gifimg_7a2b9a960ee9a98bfd25d306d55009f8.gif            {
11                string[] B = new String[A.Length];
12                for (int j = 0; j < A.Length; j++)
13img_2887d91d0594ef8793c1db92b8a1d545.gifimg_7a2b9a960ee9a98bfd25d306d55009f8.gif                {
14                    if (IsSquare(j))
15img_2887d91d0594ef8793c1db92b8a1d545.gifimg_7a2b9a960ee9a98bfd25d306d55009f8.gif                    {
16                        B[j] = (1 - Convert.ToInt32(A[j].ToString())).ToString();
17                        result++;
18                    }

19                    else
20img_2887d91d0594ef8793c1db92b8a1d545.gifimg_7a2b9a960ee9a98bfd25d306d55009f8.gif                    {
21                        B[j] = A[j].ToString();
22                    }

23                }

24                A = A + String.Join("", B);
25                //Console.WriteLine(A);
26            }

27
28            return int.Parse(A[n].ToString());
29        }

30
31        public bool IsSquare(int n)
32img_2887d91d0594ef8793c1db92b8a1d545.gifimg_7a2b9a960ee9a98bfd25d306d55009f8.gif        {
33            bool result = false;
34
35            for (int i = 0; i <= n; i++)
36img_2887d91d0594ef8793c1db92b8a1d545.gifimg_7a2b9a960ee9a98bfd25d306d55009f8.gif            {
37                if (i * i == n)
38img_2887d91d0594ef8793c1db92b8a1d545.gifimg_7a2b9a960ee9a98bfd25d306d55009f8.gif                {
39                    return true;
40                }

41            }

42
43            return result;
44        }

45    }

 

单纯为了解决方法做的,效率谈不上,性能也不好,不过刚想到一个有趣的解法,准备下午的时候抽空写写,哈哈

 

写算法纯粹是为了玩,不是要证明自己如何,大家也不必说算法到底有用无用,有用无用都是根据自己的工作来看的,不过业余时间玩玩算法,真的很好。

 

PS:写的不好,希望大家不要乱拍钻

相关文章
|
8月前
489: 平方和与立方和
489: 平方和与立方和
|
6天前
|
机器学习/深度学习 Python
北美七个站点雨量计的 2 级(L2)校准小时降水量(厘米/小时)—机载下冠层和地表下微波观测站(AirMOSS)项目
**AirMOSS: L2 小时降水量数据集 (2011-2015)** 该数据集记录了北美七个站点的2级(L2)校准小时降水量(厘米/小时),是机载下冠层和地表下微波观测站(AirMOSS)项目的一部分。每个站点安装了三个雨量计,采样始于2011年9月,并于2015年12月结束。这些数据用于研究降水对地表水分含量和地下水补给的影响,支持气候变化及生态系统研究。
61 41
你能分清比特率,波特率,信噪比,带宽,容量吗?
本文详细讲解了了物理和信号系统领域常见的关于波的几组概念,包含比特率,波特率,信噪比,带宽,容量,及对比
80 0
|
算法 Python
算法怎么算:二分为什么是闪电?
代码实现 这里我使用了两种方式,感兴趣的同学可以用更多的方式自己尝试。
40 0
【场景削减】拉丁超立方抽样方法场景削减(Matlab代码实现)
【场景削减】拉丁超立方抽样方法场景削减(Matlab代码实现)
123 0
|
机器学习/深度学习
枚 举1-1完美立方
例题1:完美立方
134 0
枚 举1-1完美立方
|
芯片
世界最小的冰箱仅1立方微米!能够瞬间制冷
世界最小的冰箱仅1立方微米!能够瞬间制冷
297 0
世界最小的冰箱仅1立方微米!能够瞬间制冷
|
传感器 Android开发 iOS开发
曝三星研发超大底6亿像素传感器
12月6日,国内知名数码博主在推特爆料称,三星正在研发6亿像素传感器,而它的尺寸更是达到了1/0.57英寸,比iPhone 12 Pro Max的传感器可能还要大一倍,甚至达到了微单的水平。
197 0
曝三星研发超大底6亿像素传感器
HDOJ 2007 平方和与立方和
HDOJ 2007 平方和与立方和
108 0
|
存储 固态存储 内存技术