博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Booksort 启发式函数很重要h(s1)<=h(s2)+cost(s1,s2);
阅读量:5925 次
发布时间:2019-06-19

本文共 4919 字,大约阅读时间需要 16 分钟。

Problem Description
The Leiden University Library has millions of books. When a student wants to borrow a certain book, he usually submits an online loan form. If the book is available, then the next day the student can go and get it at the loan counter. This is the modern way of borrowing books at the library.
There is one department in the library, full of bookcases, where still the old way of borrowing is in use. Students can simply walk around there, pick out the books they like and, after registration, take them home for at most three weeks.
Quite often, however, it happens that a student takes a book from the shelf, takes a closer look at it, decides that he does not want to read it, and puts it back. Unfortunately, not all students are very careful with this last step. Although each book has a unique identification code, by which the books are sorted in the bookcase, some students put back the books they have considered at the wrong place. They do put it back onto the right shelf. However, not at the right position on the shelf.
Other students use the unique identification code (which they can find in an online catalogue) to find the books they want to borrow. For them, it is important that the books are really sorted on this code. Also for the librarian, it is important that the books are sorted. It makes it much easier to check if perhaps some books are stolen: not borrowed, but yet missing.
Therefore, every week, the librarian makes a round through the department and sorts the books on every shelf. Sorting one shelf is doable, but still quite some work. The librarian has considered several algorithms for it, and decided that the easiest way for him to sort the books on a shelf, is by sorting by transpositions: as long as the books are not sorted,
take out a block of books (a number of books standing next to each other),
shift another block of books from the left or the right of the resulting ‘hole’, into this hole,
and put back the first block of books into the hole left open by the second block.
One such sequence of steps is called a transposition.
The following picture may clarify the steps of the algorithm, where X denotes the first block of books, and Y denotes the second block.
Of course, the librarian wants to minimize the work he has to do. That is, for every bookshelf, he wants to minimize the number of transpositions he must carry out to sort the books. In particular, he wants to know if the books on the shelf can be sorted by at most 4 transpositions. Can you tell him?
 

 

Input
The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:
One line with one integer n with 1 ≤ n ≤ 15: the number of books on a certain shelf.
One line with the n integers 1, 2, …, n in some order, separated by single spaces: the unique identification codes of the n books in their current order on the shelf.
 

 

Output
For every test case in the input file, the output should contain a single line, containing:
if the minimal number of transpositions to sort the books on their unique identification codes (in increasing order) is T ≤ 4, then this minimal number T;
if at least 5 transpositions are needed to sort the books, then the message "5 or more".
 

 

Sample Input
3
6
1 3 4 6 2 5
5
5 4 3 2 1
10
6 8 5 3 4 7 2 9 1 10
 

 

Sample Output
2
3
5 or more
***************************************************************************************************************************
***************************************************************************************************************************
1 /*  2 其中启发式函数要满足三角不等式h(s1)<=h(s2)+cost(s1,s2);  3   4 */  5 #include
6 #include
7 #include
8 #include
9 #include
10 using namespace std; 11 int n,book[30]; 12 //int i,j,k; 13 bool flag; 14 int lim; 15 bool isok() 16 { 17 int i,j,k; 18 for(i=1;i<=n;i++) 19 if(book[i]!=i) 20 return false; 21 return true; 22 } 23 int h()//启发式函数 24 { 25 int ret=0; 26 int i; 27 if(book[1]!=1) 28 ret++; 29 if(book[n]!=n) 30 ret++; 31 for(i=2;i
st) 43 { 44 for(it=st+len;it<=pos;it++) 45 book[it-len]=book[it]; 46 for(it-=len,jt=1;it<=pos;it++,jt++) 47 book[it]=tmp[jt]; 48 } 49 else 50 { 51 for(it=st-1;it>pos;it--) 52 book[it+len]=book[it]; 53 for(it=1;it<=len;it++) 54 book[it+pos]=tmp[it]; 55 } 56 } 57 void dfs(int dp) 58 { 59 if(flag) 60 return; 61 if(dp*3+h()>lim*3)//如果不满足条件,则剪枝返回 62 return; 63 if(isok()) 64 { 65 flag=true; 66 return; 67 } 68 int i,j,k; 69 int tmp[30]; 70 for(i=1;i<=n;i++) 71 tmp[i]=book[i]; 72 for(i=1;i
4||flag)117 break;118 119 }120 if(flag)121 printf("%d\n",lim);122 else123 printf("5 or more\n");124 }125 return 0;126 }
View Code

 

转载于:https://www.cnblogs.com/sdau--codeants/p/3438037.html

你可能感兴趣的文章
行列式的乘法定理
查看>>
有1000瓶水,3个瓶子可以再换1瓶,一共可以喝多少瓶?
查看>>
Search in Rotated Sorted Array ||
查看>>
NUC_HomeWork1 -- POJ2067(最短路)
查看>>
卸载mysql
查看>>
二叉树的遍历
查看>>
The Distinguish of the share or static lib in MFC
查看>>
如何导出数据库的数据词典
查看>>
linux下内存释放问题
查看>>
让Java和JavaScript进行交互
查看>>
android 上传文件
查看>>
linux逻辑卷管理
查看>>
java结合testng,利用mysql数据库做数据源的数据驱动实例
查看>>
LINQ之路12:LINQ Operators之数据转换(Projecting)
查看>>
SQL Server:数据库角色
查看>>
分享8个超棒的基于HTML5和jQuery的开发教程
查看>>
JFreeChart开发_用JFreeChart增强JSP报表的用户体验
查看>>
SpringMVC+Swagger详细整合
查看>>
计算机视觉领域最全汇总(第2部分)
查看>>
走进webpack(2)--第三方框架(类库)的引入及抽离
查看>>