数三角形问题的程序算法和数据结构

题目:数出类似下面的图中共有多少个三角形。(标号是后面我的算法用的) 手动算法:以每个最小块为单位,数出由1个、2个、……、n个单位组成的三角形数量。

提出的程序算法和数据结构:(简单的枚举,高中竞赛渣不会啥高级算法了)

  1. 输入点的数量,以及有几个点在一条线上(由一长条线连起来)的信息。例如:共11个点,0-1-7、0-2-8、……都在一条线上。
  2. 枚举所有不同的三个点的集合,判断是否为三角形:
    1. 若三点在同一条线上(即包含在上述输入的一个集合里),三角形三点不能成一条直线,否决。
    2. 若其中两个点不在任何一个相同集合里,即两点之间没有线连接,否决。
    3. 否则(两两在同一集合,三个不在同一集合),数一个三角形。

Python 渣代码实现:

#!/usr/bin/python3

######## INPUT ########
Points = 11
Sets = [
    {0,1,7}, {0,2,5,8}, {0,3,6,9}, {0,4,10},
    {1,2,3,4}, {4,5,6,7}, {7,8,9,10}
]
######## INPUT ########

test2 = lambda x, y: sum([(x in t and y in t) for t in Sets]) > 0
test3 = lambda x, y, z: sum([(x in t and y in t and z in t) for t in Sets]) > 0
result = [{a, b, c} for a in range(Points) for b in range(a+1,Points) for c in range(b+1,Points) if test2(a,b) and test2(b,c) and test2(a,c) and not test3(a,b,c)]
count = len(result)
print(count)

 

现有32位 C++ 工程修改为64位编译,以 OpenCV 为例

好久没有更新了,今天介绍一下我的一个32位OpenCV C++工程如何修改为64位下编译。

  1. 确保 Visual Studio (Visual C++) 已经带有x64编译器。

如果使用的是完整版VS,在安装时会有选项。如果使用 Express(速成版),则根据微软官方介绍,还需要安装“Windows 软件开发工具包 (SDK)”。

  1. 将工程配置修改为x64。

 

如图,首先在工具栏中,点击(默认为)“Win32”–“配置管理器”。

然后如果在“活动解决方案平台”下没有“x64”,先点击“新建”,在“键入或选择新平台”下选择“x64”并确定。

在添加x64平台之后,在下面将需要64位编译的工程后面设置为“x64”。

  1. 将外部库也设置为对应的x64版本。

这里以 OpenCV 的二进制预编译库为例,在 build 文件夹中可以找到 x64 (32位为 x86),再找到对应的编译器下对应文件,并在属性页中配置好即可。

  1. 编译程序,如果有问题则修改代码。

这里建议阅读官方的“Visual C++ 64 位迁移的常见问题”(见参考资料),尤其要检查指针、size_t和int/long类型之间的兼容性问题。

 

参考资料:

[1] 如何:针对 64 位平台配置 Visual C++ 项目 – MSDN

[2] Visual C++ 64 位迁移的常见问题 – MSDN

非营利组织或大学生免费申请Bitbucket无限账号

最近需要做一个学校的项目,用Mercurial做代码管理,在Bitbucket上申请了一个免费5用户账号,然后看到他们提供给非营利组织(NPO)和大学生免费申请无限账号(原价$80每月)的机会。

Atlassian Bitbucket网站:https://bitbucket.org

首先说一下何为无限账号:Bitbucket提供每个用户无限公开和私有库,唯一限制的是对私有库有读写权限的帐户总数。默认的免费账号,可以总共有5个帐户对你的私有库进行读写;无限账号则有无限的名额,但是每月需要付80美元的费用。

1. 首先,你需要是大学生(University student)或非营利组织(Non-profit organization member)成员的身份,而且你需要进行非开源的工程(开源工程可以使用公开库)。

2. 大学生帐户的话,需要使用学校邮箱(大陆是.edu.cn结尾,米国是.edu结尾)注册一个帐户(作为主地址,而不能作为备用地址添加到其他帐户里);非营利组织则需要准备组织的各种资料。

3. 填写对应的表格:大学生申请表 / 非营利申请表

4. 对于大学生表格的填写要求:正文部分要全部用英文填写(包括地址,翻译一下,大学生这点技能没问题吧)。学校网站要写你们学校首页,最好能把英文首页地址和其他重要信息填在附注(Additional notes)部分。至少我就这样填写,申请过了。

    对于非营利表格的填写要求,请仔细阅读申请表页面的注释。

5. 提交表格,等待人工审核。他们没说具体审核时间多少,应该一天之内都能审核完吧。审核通过后,你的账号里就会显示为无限账号(Unlimited users)的套餐了。(点击网页上的Account链接,右下方即可看见。)

注意:很幸运能有一家公司提供这么好的方案,为我等穷学生提供一个免费的Hg代码服务器。希望不是大学生和NPO身份的人、有工作有项目收入的人就不要申请了,任何服务只要国人多了都会下场悲惨,请手下留情,留给真正需要的人吧。

ZX IPv6数据库格式分析

本篇是ZX Inc的IPv6数据库中的数据存储格式分析,在多次修改和热心读者帮助下已经写出了整个结构。

ZX IPv6数据库下载地址:http://ip.zxinc.tk/

如果您想要使用本篇介绍的内容,请先参考页面上方或下方的许可协议!

以下是我以ZX 20110430版本数据库为例的分析结果:

0x0000 – 0x0003:ASCII “IPDB”(0x49 50 44 42),用来识别数据库类型。

0x0006:Byte 2(0x02),这是偏移地址长度。这个长度用于下方[1]处。

0x0007:Byte 8(0x08),这是IP地址长度。这个长度用于下方[2]处。

0x0008 – 0x000F:Int64 15725(0x6D 3D 00 00 00 00 00 00),这是数据库中的记录总条数。

0x0010 – 0x0017:HEX(0xF6 89 00 00 00 00 00 00),这是数据库地址段的开始位置。下面跳到这个地址(0x89F6)。

0x89F6 – 0x89FD [2]:IPv6(0x00 00 00 00 00 00 00 00),这是一个IPv6 /64段的记录起始地址,终止地址是下一条记录起始地址减1。

0x89FE – 0x89FF [1]:HEX(0xBB 88),这是本条记录对应的地理信息在数据库中的位置。下面跳到这个地址(0x88BB)。

0x88BB – 0x88BD:HEX(0x02 53 62),0x01和0x02开始的标志意味着跳转,后两个字节就是跳转地址。下面跳到这个地址(0x6253)。

0x6253 – 0x6263:UTF-8 String “IANA保留地址”(0x49 41 … 00),这是一个UTF8的字符串,以0x00结尾,也就是上述IP段对应的地理信息。每条IP记录对应两个地理信息的字符串(例如“山东省济南市 山东大学”),因此下面跳回到刚才的地址来获取第二段。

0x88BE:UTF-8 String(空,0x00)。如果开头不是0x01或0x02即为直接字符串,0x00结束说明为空串。之后跳回下一条IP记录(0x8A00)继续读取即可。一共读取15725次,其实只有15724条有效记录,最后一条记录(0xFF FF FF FF FF FF FF FF)对应的是数据库的版本信息,但是可以用来计算倒数第二条的结束地址(但是建议直接用这个地址作为倒数第二条记录的结束地址)。

以上就是整个数据库的数据部分格式,下方comment(不是大神就是原作者)的帮助下已经补充全了整个数据部分的内容,感谢这位未署名的游客的协助。我的这个分析是从提取数据的算法角度来写的,comment中的是整个数据库的格式总览,表达的意义是相同的。

如果您想要使用本篇介绍的内容,请先参考页面上方或下方的许可协议!

DreamSpark中国版,中国大学生免费下载微软正版软件

就当我Out了吧,今天刚在学校网络中心看见这个微软DreamSpark计划的中国版。虽然资源不算很丰富,但是校内FTP下载速度很快,而且是正版软件哦!

网址:http://dreamspark.eol.cn

目前可以用校内IP直接访问的学校有(可以按Ctrl+F搜索):天津工业大学,湖北工业大学,中国科学技术大学,山西大学,深圳大学,上海大学,长安大学,宁波大学,电子科技大学,南京大学,哈尔滨工业大学,福州大学,重庆邮电大学,东北大学,华东师范大学,北京工业大学,复旦大学,浙江大学,重庆大学,燕山大学,华南理工大学,东南大学,暨南大学,厦门大学,山东大学,北京交通大学,山东海天软件工程专修学院,郑州大学,集美大学,南京理工大学,苏州大学,西安交通大学,中山大学,太原理工大学,哈尔滨工程大学,武汉大学,中国海洋大学,上海交通大学,大连理工大学,西安电子科技大学,北京理工大学,北京科技大学,桂林理工大学,青岛科技大学,中国石油大学(华东),吉林大学。

目前提供的资源包括(经常更新):Visual Studio 2010(仅英文)、2008、2005,Expression Studio 3、4,Windows Server 2008、2008R2,Virtual PC,Internet Explorer 9,Windows CE 6.0等。

对于某些软件(例如Windows Server或CE)需要激活码,就要去国际版的DreamSpark(http://www.dreamspark.com/),申请激活码需要学校提供的@xxx.edu.cn的邮箱,或者用eol提供的邮箱。