文档章节

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
528
0
秒杀多线程第一篇 多线程笔试面试题汇总

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

晨曦之光
2012/05/21
270
0
Java类初始化顺序,大神3个示例带你躺坑。。

最近发现微信群里面有些群友在讨论类的初始化顺序,如类的静态变量、成员变量、静态代码块、非静态代码块、构造器,及继承父类时,它们的初始化顺序都是怎样的,下面我通过例子来说明这个情况...

架构之路
2017/11/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Deepin 安装wireshark抓包工具

一、关于deepin和wireshark deepin目前已经发展到15.8了,开发Android毫无压力,在四个月的使用时间里,已经非常习惯了。目前想处理一些网络问题,因此尝试在deepin上安装一个抓包工具。dee...

IamOkay
9分钟前
0
0
Docker镜像仓库服务-Nexus

建立云原生集群系统,建立自己的私有Docker镜像仓库必不可少。一方面可以加快多节点部署容器镜像的下载速度,另一方面是为了安全(容器里存储有系统所有的信息、包括密码、数据库等等,切记不...

openthings
21分钟前
0
0
127.0.0.1 和 0.0.0.0 地址的区别

1. IP地址分类 1.1 IP地址表示 IP地址由两个部分组成,net-id和host-id,即网络号和主机号。 net-id:表示ip地址所在的网络号。 host-id:表示ip地址所在网络中的某个主机号码。 即: IP-a...

华山猛男
今天
17
0
解决Unknown host 'd29vzk4ow07wi7.cloudfront.net'. You may need to adjust the proxy settings in Gradle.

把 总项目 下的 build.gradle 中的 两个 jcenter() 用 maven{ url ‘http://maven.aliyun.com/nexus/content/groups/public/’} 代替。...

lanyu96
今天
4
0
基于redis的分布式锁

redisson提供了基于redis的分布式锁实现方式,本文就尝试了下锁的使用方式。Redisson同时还为分布式锁提供了异步执行的相关方法,第二节执行介绍。 一、可重入锁验证 同一个jvm里面同一线程的...

noob_chr
今天
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部