共有回帖数 0 个
-
---------------------- ALGO_NO. 1----------------------------------
===========================BEGIN===============================
算法实现题1-1 统计数字问题
问题描述：
一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，
每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数
字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，
2，…，9。
编程任务：
给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用
到多少次数字0，1，2，…，9。
数据输入：
输入数据由文件名为input.txt的文本文件提供。
每个文件只有1 行，给出表示书的总页码的整数n。
结果输出:
程序运行结束时，将计算结果输出到文件output.txt中。输出文件共有10行，在第k行
输出页码中用到数字k-1 的次数，k=1，2，…，10。
输入文件示例 输出文件示例
input.txt
11
output.txt
1
4
1
1
1
1
1
1
1
1
===================================================================
算法实现题1-2 字典序问题
问题描述：
在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A 由26 个小
写英文字母组成A={a,b,…,z}。该字母表产生的升序字符串是指字符串中字母按照从左到
右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现1 次。例如，
a,b,ab,bc,xyz 等字符串都是升序字符串。现在对字母表A 产生的所有长度不超过6 的升序
字符串按照字典序排列并编码如下。
1 2 … 26 27 28 …
a b … z ab ac …
对于任意长度不超过6 的升序字符串，迅速计算出它在上述字典中的编码。
编程任务：
对于给定的长度不超过6 的升序字符串，编程计算出它在上述字典中的编码。
数据输入：
输入数据由文件名为input.txt的文本文件提供。
文件的第一行是一个正整数k，表示接下来共有k 行。
接下来的k行中，每行给出一个字符串。
结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。文件共有k 行，每行对应于一
个字符串的编码。
输入文件示例 输出文件示例
input.txt
2
a
b
output.txt
1
2
====================================================================
算法实现题1-3 最多约数问题
问题描述：
正整数x 的约数是能整除x 的正整数。正整数x 的约数个数记为div(x)。例如，1，2，
5，10 都是正整数10 的约数，且div(10)=4。设a 和b 是2 个正整数，a≤b，找出a 和b
之间约数个数最多的数x。
编程任务：
对于给定的2 个正整数a≤b，编程计算a 和b 之间约数个数最多的数。
数据输入：
输入数据由文件名为input.txt的文本文件提供。文件的第1 行有2 个正整数a和b。
结果输出:
程序运行结束时，若找到的a 和b 之间约数个数最多的数是x，将div(x)输出到文件
output.txt中。
输入文件示例 输出文件示例
input.txt output.txt
1 36 9
===========================================================
算法实现题1-4 金币阵列问题
问题描述：
有m x n (m=100, n=100 ) 个金币在桌面上排成一个m行n 列的金币阵列。每一枚金
币或正面朝上或背面朝上。用数字表示金币状态，0表示金币正面朝上，1 表示背面朝上。
金币阵列游戏的规则是：
（1）每次可将任一行金币翻过来放在原来的位置上；
（2）每次可任选2 列，交换这2 列金币的位置。
编程任务：
给定金币阵列的初始状态和目标状态，编程计算按金币游戏规则，将金币阵列从初始状
态变换到目标状态所需的最少变换次数。
数据输入：
由文件input.txt给出输入数据。文件中有多组数据。文件的第1行有1 个正整数k，表
示有k 组数据。每组数据的第1 行有2 个正整数m 和n。以下的m行是金币阵列的初始状
态，每行有n 个数字表示该行金币的状态，0 表示金币正面朝上，1 表示背面朝上。接着的
m行是金币阵列的目标状态。
结果输出:
将计算出的最少变换次数按照输入数据的次序输出到文件output.txt。相应数据无解时
输出-1。
输入文件示例 输出文件示例
input.txt
2
4 3
1 0 1
0 0 0
1 1 0
1 0 1
1 0 1
1 1 1
0 1 1
1 0 1
4 3
1 0 1
0 0 0
1 0 0
1 1 1
1 1 0
1 1 1
0 1 1
1 0 1
output.txt
2
-1
===============================================================
算法实现题1-5 最大间隙问题
问题描述：
最大间隙问题：给定n 个实数x1, x2 ,..., xn，求这n 个数在实轴上相邻2 个数之间的最大差值。假设对任何实数的下取整函数耗时O(1)，设计解最大间隙问题的线性时间算法。
编程任务：
对于给定的n 个实数x1,x2,...,xn，编程计算它们的最大间隙。
数据输入：
输入数据由文件名为input.txt的文本文件提供。文件的第1 行有1 个正整数n。接下来
的1 行中有n个实数 x1,x2,...,xn 。
结果输出:
程序运行结束时，将找到的最大间隙输出到文件output.txt中。
输入文件示例 输出文件示例
input.txt
5
2.3 3.1 7.5 1.5 6.3
output.txt
3.2
============================= END ============================
-------------------ALGO NO.2------------------------------
==========================================================
算法实现题2-1 输油管道问题
问题描述：
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油
田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油
井的位置,即它们的x 坐标（东西向）和y 坐标（南北向）,应如何确定主管道的最优位置,
即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道
的最优位置。
编程任务：
给定n 口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。
数据输入：
由文件input.txt 提供输入数据。文件的第1 行是油井数n，1£n£10000。接下来n 行是
油井的位置，每行2个整数x和y，-10000£x，y£10000。
结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是油井到
主管道之间的输油管道最小长度总和。
输入文件示例 输出文件示例
input.txt
5
1 2
2 2
1 3
3 -2
3 3
output.txt
6=============================================================
算法实现题2-2 众数问题
«问题描述：
给定含有n个元素的多重**S，每个元素在S中出现的次数称为该元素的重数。多重
集S中重数最大的元素称为众数。
例如，S={1，2，2，2，3，5}。
多重集S的众数是2，其重数为3。
«编程任务：
对于给定的由n 个自然数组成的多重集S，编程计算S 的众数及其重数。
«数据输入：
输入数据由文件名为input.txt的文本文件提供。
文件的第1行多重集S中元素个数n；接下来的n 行中，每行有一个自然数。
«结果输出:
程序运行结束时，将计算结果输出到文件output.txt中。输出文件有2 行，第1 行给
出众数，第2 行是重数。
输入文件示例 输出文件示例
input.txt
6
1
2
2
2
3
5
output.txt
2
3
===============================================================
算法实现题2-3 邮局选址问题
«问题描述：
在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的
街区中。用x 坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。
街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y1-y2|度量。
居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。
«编程任务：
给定n 个居民点的位置,编程计算n 个居民点到邮局的距离总和的最小值。
«数据输入：
由文件input.txt 提供输入数据。文件的第1 行是居民点数n，1=n=10000。接下来n 行
是居民点的位置，每行2 个整数x 和y，-10000=x，y=10000。
«结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是n 个居
民点到邮局的距离总和的最小值。
输入文件示例 输出文件示例
input.txt
5
1 2
2 2
1 3
3 -2
3 3
output.txt
10
==============================================================
算法实现题2-4 马的Hamilton周游路线问题
«问题描述：
8´8 的国际象棋棋盘上的一只马，恰好走过除起点外的其它63 个位置各一次，最后回
到起点。这条路线称为一条马的Hamilton 周游路线。对于给定的m´n 的国际象棋棋盘，m
和n均为大于5 的偶数，且|m-n|≤2，试设计一个分治算法找出一条马的Hamilton周游路线。
«编程任务：
对于给定的偶数m，n≥6，且|m-n|≤2，编程计算m´n 的国际象棋棋盘一条马的Hamilton
周游路线。
«数据输入：
由文件input.txt给出输入数据。第一行有2个正整数m和n，表示给定的国际象棋棋盘
由m行，每行n个格子组成。
«结果输出:
程序运行结束时,将计算出的马的Hamilton周游路线用下面的2 种表达方式输出到文件
output.txt中。
第1 种表达方式按照马步的次序给出马的Hamilton 周游路线。马的每一步用所在的方
格坐标(x，y)来表示。x表示行的坐标，编号为0，1，…，m-1；y表示列的坐标，编号为0，
1，…，n-1。起始方格为（0，0）。
第2 种表达方式在棋盘的方格中标明马到达该方格的步数。（0，0）方格为起跳步，并
标明为第1步。
输入文件示例 输出文件示例
input.txt
6 6
output.txt
(0,0) (2,1) (4,0) (5,2) (4,4) (2,3)
(0,4) (2,5) (1,3) (0,5) (2,4) (4,5)
(5,3) (3,2) (5,1) (3,0) (1,1) (0,3)
(1,5) (3,4) (5,5) (4,3) (3,1) (5,0)
(4,2) (5,4) (3,5) (1,4) (0,2) (1,0)
(2,2) (0,1) (2,0) (4,1) (3,3) (1,2)
1 32 29 18 7 10
30 17 36 9 28 19
33 2 31 6 11 8
16 23 14 35 20 27
3 34 25 22 5 12
24 15 4 13 26 21
============================================================
算法实现题2-5 半数集问题
«问题描述：
给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。
(1) n∈set(n)；
(2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；
(3) 按此规则进行处理，直到不能再添加自然数为止。
例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6 个元素。
注意半数集是多重集。
«编程任务：
对于给定的自然数n，编程计算半数集set(n)中的元素个数。
«数据输入：
输入数据由文件名为input.txt的文本文件提供。
每个文件只有1 行，给出整数n。(0n1000)
«结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。输出文件只有1 行，给出半
数集set(n)中的元素个数。
输入文件示例 输出文件示例
input.txt
6
output.txt
6
=================================================================
====================================================
算法实现题2-6 半数单集问题
«问题描述：
给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。
(1) n∈set(n)；
(2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；
(3) 按此规则进行处理，直到不能再添加自然数为止。
例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6 个元素。
注意半数集不是多重集。**中已经有的元素不再添加到**中。
«编程任务：
对于给定的自然数n，编程计算半数集set(n)中的元素个数。
«数据输入：
输入数据由文件名为input.txt的文本文件提供。
每个文件只有1 行，给出整数n。(0n201)
«结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。输出文件只有1 行，给出半
数集set(n)中的元素个数。
输入文件示例 输出文件示例
input.txt
6
output.txt
6
========================================================
算法实现题2-7 士兵站队问题
«问题描述：
在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点由整数坐标(x,y)表
示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名
士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成
(x,y),(x+1,y),…,(x+n-1,y)。如何选择x 和y的值才能使士兵们以最少的总移动步数排成一列。
«编程任务：
计算使所有士兵排成一行需要的最少移动步数。
«数据输入：
由文件input.txt 提供输入数据。文件的第1 行是士兵数n，1=n=10000。接下来n 行是
士兵的初始位置，每行2 个整数x 和y，-10000=x，y=10000。
«结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是士兵排
成一行需要的最少移动步数。
输入文件示例 输出文件示例
input.txt
5
1 2
2 2
1 3
3 -2
3 3
output.txt
8
===========================================================
算法实现题2-8 有重复元素的排列问题
«问题描述：
设R={ r1, r2, ..., rn }是要进行排列的n个元素。其中元素r1,r2,...,rn可能相同。试设计
一个算法，列出R的所有不同排列。
«编程任务：
给定n 以及待排列的n 个元素。计算出这n 个元素的所有不同排列。
«数据输入：
由文件input.txt 提供输入数据。文件的第1 行是元素个数n，1=n=500。接下来的1 行
是待排列的n个元素。
«结果输出:
程序运行结束时，将计算出的n 个元素的所有不同排列输出到文件output.txt 中。文件
最后1 行中的数是排列总数。
输入文件示例 输出文件示例
input.txt
4
aacc
output.txt
aacc
acac
acca
caac
caca
ccaa
6
===========================================================
算法实现题2-10 **划分问题
«问题描述：
n个元素的**{1,2,..., n }可以划分为若干个非空子集。例如，当n=4 时，**{1，2，3，4}可以划分为15 个不同的非空子集如下：
{{1}，{2}，{3}，{4}}，
{{1，2}，{3}，{4}}，
{{1，3}，{2}，{4}}，
{{1，4}，{2}，{3}}，
{{2，3}，{1}，{4}}，
{{2，4}，{1}，{3}}，
{{3，4}，{1}，{2}}，
{{1，2}，{3，4}}，
{{1，3}，{2，4}}，
{{1，4}，{2，3}}，
{{1，2，3}，{4}}，
{{1，2，4}，{3}}，
{{1，3，4}，{2}}，
{{2，3，4}，{1}}，
{{1，2，3，4}}
«编程任务：
给定正整数n，计算出n 个元素的**{1,2,..., n }可以划分为多少个不同的非空子集。
«数据输入：
由文件input.txt提供输入数据。文件的第1 行是元素个数n。
«结果输出:
程序运行结束时，将计算出的不同的非空子集数输出到文件output.txt中。
输入文件示例 输出文件示例
input.txt
5
output.txt
52
========================================================
算法实现题2-11 **划分问题
«问题描述：
n个元素的**{1,2,..., n }可以划分为若干个非空子集。例如，当n=4 时，**{1，2，3，4}可以划分为15 个不同的非空子集如下：
{{1}，{2}，{3}，{4}}，
{{1，2}，{3}，{4}}，
{{1，3}，{2}，{4}}，
{{1，4}，{2}，{3}}，
{{2，3}，{1}，{4}}，
{{2，4}，{1}，{3}}，
{{3，4}，{1}，{2}}，
{{1，2}，{3，4}}，
{{1，3}，{2，4}}，
{{1，4}，{2，3}}，
{{1，2，3}，{4}}，
{{1，2，4}，{3}}，
{{1，3，4}，{2}}，
{{2，3，4}，{1}}，
{{1，2，3，4}}
其中，**{{1，2，3，4}}由1 个子集组成；**{{1，2}，{3，4}}，{{1，3}，{2，
4}}，{{1，4}，{2，3}}，{{1，2，3}，{4}}，{{1，2，4}，{3}}，{{1，3，4}，{2}}，{{2，
3，4}，{1}}由2 个子集组成；**{{1，2}，{3}，{4}}，{{1，3}，{2}，{4}}，{{1，4}，
{2}，{3}}，{{2，3}，{1}，{4}}，{{2，4}，{1}，{3}}，{{3，4}，{1}，{2}}由3 个子集组
成；**{{1}，{2}，{3}，{4}}由4 个子集组成。
«编程任务：
给定正整数n 和m，计算出n 个元素的**{1,2,..., n }可以划分为多少个不同的由m 个
非空子集组成的**。
«数据输入：
由文件input.txt提供输入数据。文件的第1 行是元素个数n和非空子集数m。
«结果输出:
程序运行结束时，将计算出的不同的由m个非空子集组成的**数输出到文件output.txt
中。
输入文件示例 输出文件示例
input.txt
4 3
output.txt
6
=========================================================
算法实现题2-12 双色Hanoi塔问题
«问题描述：
设A、B、C是3 个塔座。开始时，在塔座A 上有一叠共n 个圆盘，这些圆盘自下而上，
由大到小地叠在一起。各圆盘从小到大编号为1，2，……，n，奇数号圆盘着蓝色，偶数号
圆盘着红色，如图所示。现要求将塔座A 上的这一叠圆盘移到塔座B 上，并仍按同样顺序叠
置。在移动圆盘时应遵守以下移动规则：
规则(1)：每次只能移动1 个圆盘；
规则(2)：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
规则(3)：任何时刻都不允许将同色圆盘叠在一起；
规则(4)：在满足移动规则(1)-(3)的前提下，可将圆盘移至A，B，C 中任一塔座上。
试设计一个算法，用最少的移动次数将塔座A 上的n个圆盘移到塔座B 上，并仍按同样
顺序叠置。
«编程任务：
对于给定的正整数n，编程计算最优移动方案。
«数据输入：
由文件input.txt给出输入数据。第1 行是给定的正整数n。
«结果输出:
将计算出的最优移动方案输出到文件output.txt。文件的每一行由一个正整数k 和2 个
字符c1 和c2组成，表示将第k个圆盘从塔座c1移到塔座c2上。
输入文件示例 输出文件示例
input.txt
3
output.txt
1 A B
2 A C
1 B C
3 A B
1 C A
2 C B
1 A B
=====================================================
算法实现题2-13 标准2维表问题
«问题描述：
设n 是一个正整数。2 x n 的标准2 维表是由正整数1，2，…，2n 组成的2 x n 数组，该数组的每行从左到右递增，每列从上到下递增。2 x n的标准2 维表全体记为Tab(n)。例如，
当n=3时Tab(3)如下：
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5
4 5 6 3 5 6 3 4 6 2 5 6 2 4 6
«编程任务：
给定正整数n，计算Tab(n)中2 x n的标准2 维表的个数。
«数据输入：
由文件input.txt给出输入数据。第一行有1 个正整数n。
«结果输出:
将计算出的Tab(n)中2 x n的标准2 维表的个数输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
3
output.txt
5
=========================================================
算法实现题2-14 整数因子分解问题
«问题描述：
大于1 的正整数n可以分解为：n=x1*x2*…*xm。
例如，当n=12 时，共有8 种不同的分解式：
12=12；
12=6*2；
12=4*3；
12=3*4；
12=3*2*2；
12=2*6；
12=2*3*2；
12=2*2*3。
«编程任务：
对于给定的正整数n，编程计算n共有多少种不同的分解式。
«数据输入：
由文件input.txt给出输入数据。第一行有1 个正整数n (1≤n≤2000000000)。
«结果输出:
将计算出的不同的分解式数输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
12
output.txt
8
=================END===============================
楼主 2016-04-28 11:31 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
