Sorting an array can be done by swapping certain pairs of adjacent entries in the array. This is the fundamental technique used in the well-known bubble sort. If we list the identities of the pairs to be swapped,
in the sequence they are to be swapped, we obtain what might be called a swap map. For example, suppose we wish to sort the array A whose elements are 3, 2, and 1 in that order. If the subscripts for this array are 1, 2, and 3, sorting the array can be accomplished
by swapping A2 and A3, then swapping A1 and A2, and finally swapping A2 and A3. If a pair is identified in a swap map by indicating the subscript of the first element of the pair to be swapped, then this sorting process would be characterized with the swap
map 2 1 2.
It is instructive to note that there may be many ways in which swapping of adjacent array entries can be used to sort an array. The previous array, containing 3 2 1, could also be sorted by swapping A1 and A2, then
swapping A2 and A3, and finally swapping A1 and A2 again. The swap map that describes this sorting sequence is 1 2 1.
For a given array, how many different swap maps exist? A little thought will show that there are an infinite number of swap maps, since sequential swapping of an arbitrary pair of elements will not change the order
of the elements. Thus the swap map 1 1 1 2 1 will also leave our array elements in ascending order. But how many swap maps of minimum size will place a given array in order? That is the question you are to answer in this problem.
Input
The input data will contain an arbitrary number of test cases, followed by a single 0. Each test case will have a integernthat gives the size of an array, and will be followed by theninteger
values in the array.
Output
For each test case, print a message similar to those shown in the sample output below. In no test case willnbe larger than 5.
Sample Input
2 9 7
2 12 50
3 3 2 1
3 9 1 5
0
Sample Output
There are 1 swap maps for input data set 1.
There are 0 swap maps for input data set 2.
There are 2 swap maps for input data set 3.
There are 1 swap maps for input data set 4.
又是回溯,求交换排序的不同方案次数。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int arry[10];
int n,s;
bool sorted()
{
for(int i=0;i<n-1;i++)
{
if(arry[i]>arry[i+1])
return false;
}
return true;
}
void dfs()
{
if(sorted())
s++;
else
{
for(int i=0;i<n-1;i++)
{
if(arry[i]>arry[i+1])
{
swap(arry[i],arry[i+1]);
dfs();
swap(arry[i],arry[i+1]);
}
}
}
}
int main()
{
int t=0;
while(cin>>n&&n)
{
int i,j,k;
for(i=0;i<n;i++)
cin>>arry[i];
s=0;
if(!sorted())
dfs();
cout<<"There are "<<s<<" swap maps for input data set "<<++t<<"."<<endl;
}
return 0;
}
分享到:
相关推荐
Mapping the Gnutella Network 对于Gnutella网络的详细介绍
Desktop GIS Mapping the Planet with Open Source Tools.pdf
delphi 2010升级到xe8后,decodestring汉字出现:No mapping for the.mht
Title:3D Robotic Mapping The Simultaneous Localization and Mapping Problem with Six Degrees of Freedo ISBN-13 书号:9783540898832 Author 作者:Nuchter, Andreas 出版社:Springer Publication Date 出版日期...
Desktop GIS is a comprehensive survey of open source software for GIS users. Everyone from casual ...anyone interested in a hands-on approach to learning the latest in open source GIS technology.
The second section presents the theory of bump mapping. The third section reviews several existing hardware bump-mapping techniques. The fourth section describes the cube map texturing and “register...
Generic Mapping Tools (GMT) 中文手册
Experimental results demonstrate the efficiency and precision of the proposed method by mapping the Ada Byron building at our campus. We also analyze, using simulations, the precision and convergence...
Projective texture mapping refers both to the way texture coordinates are assigned to vertices, and the way they are computed during rasterization of primitives. We usually think of texture mapping as...
绘制东海硝酸盐长江口海域的不同季节不同深度层次的大面分布图,利用nc文件:woa18_all_n16_01.nc,进行绘制
matlab_mapping_toolbox extracted from version 2019b
ISO IEC TR 27023:2015 Information technology — Security techniques — Mapping the revised editions of ISO IEC 27001 and ISO IEC 27002 - 完整英文版(24页).pdf
图优化slam学习常备,英文版,适合学习理论的广大slam学习者使用
Indoor-Mapping-Using-the-VLC-Channel-State-Information-master源码
一、solidity中,映射的关键字为mapping,首先我们先来定义两个mapping, mapping(address =>uint) idmapping和mapping(uint =>string) namemapping。idmapping用来表示地址变量和整型变量的对应关系,在注册过程中...
XI PI MAPPING开发必须jar包 import com.sap.aii.mapping.api.*; import com.sap.aii.mapping.api.*; import com.sap.aii.mapping.lookup.*; import com.sap.aii.mappingtool.tf7.rt.*;
it gives ofdm mapping
单应矩阵 homography matrix的详细讲解, 推导, 求解方法. 94页
arcgis103.1版本插入动态表格,制图时插入动态表格,Esri Mapping and Charting Solutions。
arcgis10.2.2动态表格扩展模块,mapping and charting solutions