`
zwhc
  • 浏览: 266209 次
  • 性别: Icon_minigender_1
  • 来自: 福州
社区版块
存档分类
最新评论

百亿人口,选八十万移民的解法。

阅读更多
地球人口越来越多,终于达到了100亿了。还好,发现了一颗适合人类居住的星球。现在,需要派遣八十万个人先期进驻。如何选出这八十万的人呢?

算法描述:
1、有六个数 0 1 2 3 4 5,随机数为 4 2 2 1 0 0。
2、第一次从六个数里取随机数,为4,则将第4个数取出,变为0123*5,取出的数为 4
3、而后,将第5个数交换到第4个数的位置上,即数字变为 01235
4、第二次从五个数里取随机数,为2,则将第2个数取出,变为01*35,取出的数为 2
5、而后,将第4个数交换到第2个数的位置上,即数字变为 0153
6、第三次从四个数里取随机数,为2,则将第2个数取出,变为01*3,取出的数为 5
7、而后,将第3个数交换到第2个数的位置上,即数字变为 013
8、第四次从三个数里取随机数,为1,则将第1个数取出,变为0*3,取出的数为 1
9、而后,将第2个数交换到第1个数的位置上,即数字变为 03
10、第五次从两个数里取随机数,为0,则将第0个数取出,变为*3,取出的数为 0
11、而后,将第1个数交换到第0个数的位置上,即数字变为 3
12、第六次随机数为0,则将第0个数取出,变为*,取出的数为 3

即,取到的数为 425103。

另外,代码有错误,已更改。

package test;

import java.util.Hashtable;
import java.util.Random;
import java.util.Vector;

public class DaLuan {

	/**
	 * 长度为 s 的序列,从中随机抽取 n 个数据。
	 * 算法:
	 * 1、先在 0-s 里随机取一数 [R];
	 * 2、将 [R] = [0], [0]将不再使用
	 * 3、先在 1-s 里随机取一数 [R1];
	 * ...  
	 * @param s
	 * @param n
	 * @return
	 */
	private static int[] getRandom(int s, int n)
	{
		if(s<=0 || n<=0)
		{
			throw new RuntimeException("必须:s>0 且 n>0 ");
		}

		if(s<n)
		{
			throw new RuntimeException("必须:s>=n ");
		}
		
		int[] data = new int[n];
		int[] temp = new int[s];
		for(int i=0; i<s; i++)
		{
			temp[i] = i;
		}
		
		Random random = new Random();
		random.setSeed(System.currentTimeMillis());
		
		for(int i=0; i<n; i++)
		{
			int idx = random.nextInt(s-i)+i;
			data[i] = temp[idx];
			temp[idx] = temp[i];
		}
		
		return data;
	}
	
	private static void print(int[] data)
	{
		for(int i=0; i<data.length; i++)
		{
			System.out.println(data[i]);
		}
	}
	
	/**
	 * 长度为 s 的序列,从中随机抽取 n 个数据。
	 * 算法:
	 * 1、先在 0-s 里随机取一数 [R];
	 * 2、将 [R] = [0], [0]将不再使用
	 * 3、先在 1-s 里随机取一数 [R1];
	 * ...  
	 * 
	 * 并列出随机数取了三次以上的数据
	 * @param s
	 * @param n
	 * @return
	 */
	private static int[] getRandom02(int s, int n)
	{
		if(s<=0 || n<=0)
		{
			throw new RuntimeException("必须:s>0 且 n>0 ");
		}

		if(s<n)
		{
			throw new RuntimeException("必须:s>=n ");
		}
		
		int[] data = new int[n];
		int[] temp = new int[s];
		int[] selectCount = new int[s]; 
		for(int i=0; i<s; i++)
		{
			temp[i] = i;
			selectCount[i] = 0;
		}
		
		Random random = new Random();
		random.setSeed(System.currentTimeMillis());
		
		for(int i=0; i<n; i++)
		{
			int idx = random.nextInt(s-i)+i;
			data[i] = temp[idx];
			selectCount[idx]++;
			if(selectCount[idx]>1) //并列出随机数取了三次以上的数据
			{
				System.out.println(selectCount[idx] + ":" + idx);
			}
			temp[idx] = temp[i];
		}
		
		return data;
	}
	
	/**
	 * 这个版本针对的是从百亿级数据里取数据的。
	 * 
	 * 长度为 s 的序列,从中随机抽取 n 个数据。
	 * 算法:
	 * 1、先在 0-s 里随机取一数 [R];
	 * 2、将 [R] = [0], [0]将不再使用
	 * 3、先在 1-s 里随机取一数 [R1];
	 * ...  
	 * @param s
	 * @param n
	 * @return
	 */
	private static long[] getRandom03(long s, int n)
	{
		if(s<=0 || n<=0)
		{
			throw new RuntimeException("必须:s>0 且 n>0 ");
		}

		if(s<n)
		{
			throw new RuntimeException("必须:s>=n ");
		}
		
		long[] data = new long[n];
		Hashtable<Long, Long> ht = new Hashtable<Long, Long>();
		
		Random random = new Random();
		random.setSeed(System.currentTimeMillis());
		
		for(int i=0; i<n; i++)
		{
			long l = random.nextLong();
			if(l<0)
			{
				l= Math.abs(l);
			}
			long idx = l % (s-i);
			
			if(ht.get(idx)==null)
			{
				data[i] = idx;
			}
			else
			{
				data[i] = ht.get(idx);
			}
			
			if(ht.get(s-i-1)==null)
			{
				ht.put(idx, s-i-1);
			}
			else
			{
				ht.put(idx, ht.get(s-i-1));
			}
		}
		return data;
	}	


	public static void main(String[] args)
	{
		System.out.println(Runtime.getRuntime().maxMemory());
		
		//Collections.shuffle(null);
		
		//print(getRandom02(3000000, 2500));
		//getRandom03(10000000000L, 1000000);
		getRandom03(10000000000L, 800000);
		//getRandom03(10000000000L, 1000000); //需要设置vm参数 -Xms64M -Xmx256M
	}
}
0
1
分享到:
评论
3 楼 zwhc 2010-08-06  
fy616508150 写道
没看明白``题目的意思``


就是从百亿里,取八十万的数据。

题目的写法,只是为了增加趣味性而已。
2 楼 fy616508150 2010-08-06  
没看明白``题目的意思``
1 楼 zwhc 2010-08-06  
当然,还可以分段取。比如,将 100亿分成 80万个组,即每组 12500。从中选一个即可。

还可以象股票新股摇号那样。

相关推荐

    世界人口数据集(总人口、密度、土地面积、移民、生育率等数据)

    世界各国/实体的世界人口数据。 它共包含235条记录,11列包含2020年前总人口、年变化、净变化、密度、土地面积、移民、生育率、中年人、城市人口和世界人口份额的数据。

    1950-2021世界各国人口总量、出生、死亡及移民数据集.rar

    背景描述1950年后,国际时局稳定,人口成为逐年关注的重点话题,通过人口的波动,可以推测各国各年的大事件影响,以及出生,死亡,移民等数据,分析国力与影响力;数据说明1950-2021世界各国人口总量、出生、死亡及...

    世界各国人口数据.zip

    10. **人口政策**:各国根据自身的人口状况制定相应的人口政策,如计划生育、鼓励生育、移民政策等,以应对人口问题。 综上所述,"世界各国人口数据.zip"这个压缩包中的数据对于研究全球人口趋势、政策制定者制定...

    农村移民安置规划设计

    农村移民安置规划设计是针对因各种原因(如水利建设、自然灾害防治等)需要迁移的农村居民进行的规划工作,旨在确保移民的生活质量和经济稳定。这项工作涉及到多个层面,包括实物指标数据管理、社会经济数据管理以及...

    2010-2017年美国移民数据

    而在美国人口调查方面,这些数据可以帮助我们理解人口结构,移民来源地,移民目的,以及移民对美国社会和经济的影响。 标签 "xlsx" 指的是这些数据是以Microsoft Excel的.xlsx文件格式存储的。Excel是一种常见的...

    matlab开发-美国人口增长模型

    标题“matlab开发-美国人口增长模型”表明我们要探讨的是使用MATLAB编程语言构建的用于预测美国人口增长的数学模型。MATLAB是一种强大的数值计算和数据可视化工具,它被广泛应用于科学计算、工程分析和教育领域。在...

    水库移民安置风险分析评价

    随着我国大中型水利水电工程的大量建设,需要迁移的人口数量急剧增加,移民安置的风险管理变得更加复杂和重要。冯雪在其研究中提出了一个风险管理体系,以分析和评价水库移民安置过程中的各种风险因素。 水库移民...

    水库移民GIS系统

    骋天水库移民GIS应用系统是以地理信息系统(GIS)和数据库为开发平台的可视化动态信息管理系统,通过互联网为广大公众提供移民信息的动态查询功能,为各级水利移民工作者提供可视化的网络业务处理平台。 骋天通过该...

    人口增长模型数学建模论文

    该文主要探讨了人口增长模型的数学建模方法,针对中国人口问题,通过最小二乘拟合法预测1999年至2008年间的人口发展趋势。以下是文章中涉及的关键知识点: 1. **人口增长模型**:人口增长模型是描述人口数量随时间...

    人口预测软件

    3. **政策模拟**:软件可以模拟不同政策对人口结构和数量的影响,如生育政策、移民政策等,帮助决策者评估政策效果。 4. **城市规划**:在城市规划中,人口预测是必不可少的环节,软件能为城市基础设施建设、公共...

    2020中国都市圈“新移民”吸引力报告.pdf

    2020年中国都市圈“新移民”吸引力报告通过深入研究和分析,揭示了都市圈化背景下,中国流动人口群体的新趋势和特点,以及30个核心都市圈对“新移民”的吸引力。报告详细探讨了中国城市人口流动的新趋势,对“新移民...

    八年级地理上册人种和人口合理人口政策材料题中图PPT学习教案.pptx

    标题和描述中提到的PPT学习教案主要关注的是八年级地理上册中关于人种、人口以及合理人口政策的主题。这个教学材料通过分析不同国家的人口情况,探讨了人口增长速度对国家发展的影响,旨在教育学生理解人口问题的...

    数学建模,人口模型讲义

    《数学建模与人口模型讲义》是一份深入探讨数学建模在人口研究中的应用的资料,主要聚焦于如何利用数学工具理解和预测人口动态。在当今社会,人口问题已成为全球关注的焦点,从人口增长、老龄化到迁移模式,都需要...

    近代山东移民迁陕原因探析

    移民持续时间长,影响深远,形成了众多的山东庄,山东移民后裔在关中地区繁衍生息,数量达到三十多万。这不仅改变了关中的人口结构,也带来了山东地区的文化传承,影响了当地的社会经济和文化发展。 总结来说,清末...

    人口预测建模讲解与代码

    在本主题"人口预测建模讲解与代码"中,我们将深入探讨如何利用数学建模方法对人口发展趋势进行预测。这是一门结合统计学、计算机科学和应用数学的学科,旨在通过对历史人口数据的分析,构建预测模型,以预估未来人口...

    2007全国数模赛中国人口增长预测

    【摘要分析】 这篇摘要主要介绍了2007年全国数模赛中的一项研究,该研究构建了两个模型来预测中国...然而,任何模型都有其局限性,实际人口动态可能受到模型未考虑的多种因素影响,如移民政策、科技进步和经济波动等。

    胡润研究院与汇加移民发布《中国投资移民白皮书》.pdf

    胡润研究院与汇加移民发布《中国投资移民白皮书》.pdf

    美国2010-2015年人口普查数据

    2. **数据内容**:2010-2015年的数据可能包括年龄、性别、种族、族裔、教育水平、职业、收入、家庭结构、婚姻状况、住房状况、出生地、移民状况等多种人口统计指标。这些数据通常以表格形式存在,可能包含国家、州、...

Global site tag (gtag.js) - Google Analytics