文档章节

2012百度之星第二场初始题-1

李勇2
 李勇2
发布于 2015/03/02 09:38
字数 962
阅读 24
收藏 0

问题描述:

    给定n个正整数, 要求从这些正整数中 取出若干个, 对他们进行xor(异或)计算, 寻找可能产生的最大值。


    xor运算有点类似于加法运算,但是它操作的是二进制的数字; 例如 101010 xor 111000 = 010010

    ok解决任何问题,首先找出一些实际的例子, 例如在 集合 {5, 3} 中寻找;

    首先写成2进制的形式:

    1001  = 5

    0011  = 3

    有点类似于一个现行方程组矩阵的样子;

    而我们寻找的解是什么呢? 是这个方程组的xor 下的线性变化 产生的最大值 ?

    为什么? 

        xor 满足交换律 和 结合律;

        线性变化,就是在不同的方程之间使用xor操作, 用产生的结果替换 原来的方程, 这个新的方程组和原来的方程组等价;

             为什么等价?

                      A xor B = C   =>  C xor B = A   C xor A = B  

                      原来的方程组可以逆向得到, 所以等价


   怎么得到最大值?

            采用高斯消元法 可以得到一个等价方程组, 例如集合{101010,  111000,  110101,  001111} 

            消元之后的结果是:

                100101
                010000
                001101
                000010

             这个方程组的每个方程的维度是6, 但是整个方程组的度 是 4; 即六维空间里面的一个4维的对象;

             这4个方程任意xor的最大值是就是这四个方程全部xor的结果:

            111010

            为什么? 比如第四列为0, 为了使第四列为1, 必须舍弃 第1 或 3 方程, 显然都不行;

             而如果使6列为1, 需要舍弃 1 或者 3方程, 显然也不行;

             而如果舍弃某个 方程,也不合适, 会导致某一位变成0

             而由 xor的交换律 和结合律 可以知道: 所有组合的最后化简的结果 每个方程最多出现一次 因为 A xor A = 0   0 xor B = B


如何证明这四个方程组的最大值就是 原来集合中的最大值呢? 

             由xor的计算的可逆性,我们可以知道:

             因为在集合 {101010, 111000, 110101, 001111} 中的任意元素都可以由最后我们计算的四个方程表示;

             所以集合中任意元素组合的xor结果都可以用 最后计算的4个方程表示。

             而这4个方程xor的结果 最大值是 111010  

             

上面的例子:

           这个例子是方程的个数小于 维度的一个例子;  可以有3种情况:

           个数 小于 维度;  独立方程的个数 就是原方程组方程的个数;

           个数 等于 维度;   独立方程的个数 等于 维度

           个数 大于 维度;   独立方程的个数 等于 维度


而要计算次大值:

           可以从化简结果中舍弃一个最小的方程; 

           为什么?

                  舍弃最小的方程, 将会导致 某一位 变成0, 而这一位是独立的; 其它位不会变化;

                  如果要使其它位变化, 

                                           要么这个位本身是独立的, 那么 就比舍弃最小的要大;

                                           要么这个位依赖于其它位, 那么要么依赖于最小的独立位, 要么依赖于其它的独立位, 这样产生的结果要么等价于舍弃最小的方程,要么等价于舍弃其它方程, 都不合适



产生结果的实际个数:

           4个方程的 任意组合 产生的结果的个数 是 2^4 = 16 (包含一个空集合); 也就是4个方程的任意组合结果有16个

           对于一个32位二进制数, 最多有 2^32 种结果, 也就是32位二进制数本身的空间;

           

 

           

           

   

             

   


本文转载自:http://blog.csdn.net/liyong748/article/details/7627866

共有 人打赏支持
李勇2

李勇2

粉丝 46
博文 189
码字总数 62209
作品 0
广州
程序员
18届清华硕士狂拿18家互联网公司offer

2018校招总结(外企,国内大公司,国内创业公司) 本篇是我参加2018春招实习和秋招的求职经历,除了笔试面试中遇到的一些问题,更多的是一些个人想法。 春招和秋招面了不少公司,实习offer有...

野梦M
2017/12/18
0
1
报名 | 第14届百度之星报名正热,PaddlePaddle解锁中国式深度学习

  2018 百度之星大赛于 7 月 4 日正式启动报名,涵盖百度之星·程序设计大赛与百度之星·开发者大赛两大子赛事,怀揣梦想的技术咖们,还在等什么呢?   程序设计大赛与开发者大赛两项赛事...

机器之心
07/31
0
0
秒杀多线程第一篇 多线程笔试面试题汇总

系列前言 本系列是本人参加微软亚洲研究院,腾讯研究院,迅雷面试时整理的,另外也加入一些其它IT公司如百度,阿里巴巴的笔试面试题目,因此具有很强的针对性。系列中不但会详细讲解多线程同...

彭博
2012/04/12
441
0
秒杀多线程第一篇 多线程笔试面试题汇总

系列前言 本系列是本人参加微软亚洲研究院,腾讯研究院,迅雷面试时整理的,另外也加入一些其它IT公司如百度,阿里巴巴的笔试面试题目,因此具有很强的针对性。系列中不但会详细讲解多线程同...

晨曦之光
2012/05/21
159
0
秒杀多线程第一篇 多线程笔试面试题汇总

系列前言 本系列是本人参加微软亚洲研究院,腾讯研究院,迅雷面试时整理的,另外也加入一些其它IT公司如百度,阿里巴巴的笔试面试题目,因此具有很强的针对性。系列中不但会详细讲解多线程同...

长平狐
2012/12/10
136
0

没有更多内容

加载失败,请刷新页面

加载更多

Java GC机制详解

垃圾收集 Garbage Collection 通常被称为“GC”,本文详细讲述Java垃圾回收机制。 导读: 1、什么是GC 2、GC常用算法 3、垃圾收集器 4、finalize()方法详解 5、总结--根据GC原理来优化代码 ...

小刀爱编程
16分钟前
1
0
ORACEL学习--理解over()函数

二、理解over()函数 1.1、两个order by的执行时机 分析函数是在整个sql查询结束后(sql语句中的order by的执行比较特殊)再进行的操作, 也就是说sql语句中的order by也会影响分析函数的执行结果...

spinachgit
18分钟前
1
0
抽象语法树

import asttree = ast.parse('def hello_word(): print("hello world!")')def hell_word(): print(1)print(ast.dump(tree)) 语法树 可以基于这个实现另外一种编程语言...

colin_86
19分钟前
1
0
Akka查询设备组《fourteen》译

加入以下依赖到项目中: 介绍: 到目前为止,我们看到的会话模式很简单,因为它们要求Actor保持很少或没有状态。 特别: 设备actor返回一个读数,不需要更改状态。 记录温度,更新单个字段。...

woshixin
26分钟前
1
0
wait、notify、notifyAll 的用法

wait()、notify()、notifyAll()是三个定义在Object类里的方法,用来控制线程的状态。这三个方法最终调用的都是jvm的native方法, 随着jvm运行平台的不同可能有些许差异。 wait(): 使持有该对...

noob_fly
28分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部