文档章节

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

粉丝 45
博文 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
System center 2012 R2 实战四、sharepoint2010服务器场介绍及安装

上一章我们安装了sharepoint2010,只是非常简单的安装上了,并且进行了几个简单的排错,然后又集成了一下reporting services,还记得吗,上一章我们安装sharepoint的时候选中的是独立安装,也...

科技小能手
2017/11/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Nginx防盗链、访问控制、Nginx解析PHP相关配置、Nginx代理

Nginx防盗链 在配置文件里写入以下内容: 用curl测试 访问控制 Nginx限制某些IP不能访问或者只允许某些IP访问。 配置文件写入如下内容: allow 表示允许访问的IP,deny限制访问的IP。 匹配正...

黄昏残影
16分钟前
0
0
自己动手实现RPC服务调用框架

转载 TCP的RPC 引言 本文利用java自带的socket编程实现了一个简单的rpc调用框架,由两个工程组成分别名为battercake-provider(服务提供者)、battercake-consumer(服务调用者)。 设计思路...

雨中漫步的鱼
19分钟前
0
0
Centos6.x安装之后的9件事

Centos6.x安装之后的9件事 这些不是必须都做的,只不过是我个人的习惯,在此记录一下。 1.修改yum源到国内 CentOS系统更换软件安装源 备份你的原镜像文件,以免出错后可以恢复。 mv /etc/yu...

叶云轩
24分钟前
6
0
springboot2 使用jsp NoHandlerFoundException

开发图片上传功能,为验证测试功能是否正常,使用JSP编写表单提交进行测试 开发完成后,请求API提示如下异常: No mapping found for HTTP request with URI [/WEB-INF/jsp/avatar_upload.j...

showlike
30分钟前
0
0
springboot踩坑记--springboot正常启动但访问404

一 spring boot的启动类不能直接放在main(src.java.main)这个包下面,把它放在有包的里面就可以了。 二 正常启动了,但是我写了一个controller ,用的@RestController 注解去配置的controlle...

onedotdot
31分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部