《算法分析与设计》练习5
问题A
栋栋和李剑已经大四了，想要出去找房子住。他们一共看中了n套房子。其中第i套房子已经住了ai个人了，它最多能住bi个人。栋栋和李剑想要住在一起，那么请问他们有几套可以选择的房子？
解题思路：bi-ai>=2,则该套房子可以住
import java.util.Scanner;
public class A {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
while(scanner.hasNext()&&(n>0)){
int k=0;
int i = scanner.nextInt();
n--;
int a[][] = new int[i][2];
for(int j = 0;j<i;j++){
for(int h=0;h<2;h++){
a[j][h] = scanner.nextInt();
}
}
for(int j = 0;j<i;j++){
if((a[j][1]-a[j][0])>=2){
k++;
}
}
System.out.println(k);
}
}
}
问题B
有一个rand(n)的函数，它的作用是产生一个在[0,n)的随机整数。现在有另外一个函数，它的代码如下：
int random(int n, int m)
{
return rand(n)+m;
}
显而易见的是函数random(n,m)可以产生任意范围的随机数。现在问题来了，如果我想要产生范围在[a,b)内的一个随机数，那么对应的n，m分别为多少？
解题思路：找出a,b和n,m 之间的关系即可；a=m,b=n+m;
import java.util.Scanner;
public class MainB {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int k = scanner.nextInt();
while(scanner.hasNext()&&(k>0)){
int a = scanner.nextInt();
int b = scanner.nextInt();
if(a>b){
int t = a;
a=b;
b=t;
}
int m = a;
int n = b-a;
k--;
System.out.println(n+" "+m);
}
}
}
问题C
Kimi生活在充满危险和阴谋的年代。为了生存，他首次发明了密码，用于军队的消息传递。假设你是军团中的一名军官，需要把发送来的消息破译出来、并提供给你的将军。
消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第5个字母替换（例如：消息原文中的每个字母A 都分别替换成字母F），其他字符不变，并且消息原文的所有字母都是大写的。密码中的字母与原文中的字母对应关系如下。
密码字母：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
原文字母：V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
解题思路：找到解密字母和加密字母之间关系即可
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()){
String str = scanner.nextLine();
char array[] = str.toCharArray();
int x = 'V'-'A';
int y = 'F'-'A';
for(int i = 0;i<array.length;i++){
if(array[i]>='A'&&array[i]<='E'){
array[i]=(char) (array[i]+x);
}else if(array[i]>='F'&&array[i]<='Z'){
array[i]=(char) (array[i]-y);
}
}
for(int i = 0;i<array.length;i++){
System.out.print(array[i]);
}
System.out.println();
}
}
}
问题D
从键盘上输入10个整数，用冒泡法对这10个数进行排序（由小到大）。
1.原理：比较两个相邻的元素，将值大的元素交换到右边
2.思路：依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。
(1)第一次比较：首先比较第一和第二个数，将小数放在前面，将大数放在后面。
(2)比较第2和第3个数，将小数 放在前面，大数放在后面。
…
(3)如此继续，知道比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成
(4)在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以在比较第二趟的时候，最后一个数是不参加比较的。
(5)在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较的。
(6)依次类推，每一趟比较次数减少依次
import java.util.Scanner;
public class MainD {
//冒泡排序
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n[] = new int[10];
for(int i=0;i<10;i++){
n[i] = scanner.nextInt();
}
for(int i=9;i>=0;i--){
for(int j=0;j<i;j++){
if(n[j]>n[j+1]){
int t = n[j];
n[j] = n[j+1];
n[j+1] = t;
}
}
}
for(int i=0;i<10;i++){
System.out.println(n[i]);
}
}
}
问题E
输入n个正整数，用选择排序输出升序排列后的结果
解题思路：即找到最大值和最后一个交换，再在剩下的n-1个数中继续选一个最大值和倒数第2个交换，如此循环，直至全部有序。
import java.util.Scanner;
public class MainE {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int x[] = new int[n];
int t ;
for(int i=0;i<n;i++){
x[i] = scanner.nextInt();
}
for(int j=(n-1);j>=0;j--){
t = 0;
for(int i=0;i<=j;i++){
if(x[i]>x[t]){
t=i;
}
}
//将大值与后面的数交换
int h = x[t];
x[t] = x[j];
x[j] = h;
}
for(int i=0;i<n;i++){
System.out.print(x[i]+" ");
}
}
}
问题F
输入10个整数，彼此以空格分隔。重新排序以后输出(也按空格分隔)，要求:
1.先输出其中的奇数,并按从大到小排列；
2.然后输出其中的偶数,并按从小到大排列。
解题思路：先判断奇数和偶数，分布存放，再分别进行比较。
import java.util.Scanner;
public class MainF {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()){
int a=0,b=0;
int z[] = new int[10];
for(int i=0;i<10;i++){
z[i]=scanner.nextInt();
if(z[i]%2==0){
b++;
}else{
a++;
}
}
int x[] = new int[a];//奇数
int y[] = new int[b];//偶数
a = 0;
b = 0;
for(int i=0;i<10;i++){
if(z[i]%2==0){
y[b]=z[i];
b++;
}else{
x[a] = z[i];
a++;
}
}
//奇数从大到小排列
for(int i=0;i<x.length;i++){
for(int j=(i+1);j<x.length;j++){
if(x[i]<x[j]){
int t = x[i];
x[i] = x[j];
x[j] = t;
}
}
}
for(int i=0;i<x.length;i++){
System.out.print(x[i]+" ");
}
//偶数从小到大排列
for(int i=0;i<y.length;i++){
for(int j=(i+1);j<y.length;j++){
if(y[i]>y[j]){
int t = y[i];
y[i] = y[j];
y[j] = t;
}
}
}
for(int i=0;i<y.length;i++){
System.out.print(y[i]+" ");
}
System.out.println();
}
}
}
问题G
n 个人站成一行玩一个报数游戏。所有人从左到右编号为 1 到 n。游戏开始时，最左边的人报 1，他右边的 人报 2，编号为 3 的人报 3，等等。当编号为 n 的人（即最右边的人）报完 n 之后，轮到他左边的人（即编号为 n-1 的人）报 n+1，然后编号为 n-2 的人报 n+2，以此类推。当最左边的人再次报数之后，报数方向又变成从左 到右，依次类推。
为了防止游戏太无聊，报数时有一个特例：如果应该报的数包含数字 7 或者是 7 的倍数，他应当用拍手代 替报数。下表是 n=4的报数情况（X表示拍手）。当编号为 3 的人第 4 次拍手的时候，他实际上数到了 35。
给定 n，m和 k，你的任务是计算当编号为 m的人第 k 次拍手时，他实际上数到了几。
解题思路：
1.将数据按照如下图所示存储：偶数行（从0开始）：列数从小到大逐次+1（2到4）；奇数行：列数从大到小逐次+1（从3到1）。
2.判断标号（列号）为m的数组中含有7和7 的倍数的数字出现了几次
import java.util.Scanner;
public class MainG {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int h=10;
while(scanner.hasNext()&&h>0){
int n = scanner.nextInt();
int m = scanner.nextInt();
int k = scanner.nextInt();
h--;
if(n==0&&m==0&&k==0){
break;
}if(n<2||n>100||k<1||k>100||m<1||n<m){
break;
}else{
fun(n,m,k);
}
}
}
private static void fun(int n, int m, int k) {
int x[][] = new int[10000][n];
x[0][0] = 1;
int a=2;
int b =0;//第几次拍手
for(int i=0;i<10000;i++){
if(i%2==0){//偶数行 列数从小到大
for(int j=1;j<n;j++){
x[i][j]=a;
a++;
}
}else{//奇数行 列数从大到小
for(int j=(n-2);j>=0;j--){
x[i][j]=a;
a++;
}
}
}
for(int i=0;i<10000;i++){
int flag = 0;
String str = String.valueOf(x[i][m-1]);
char[] str1 = str.toCharArray();
//判断是否有7
for(int j=0;j<str1.length;j++){
if(str1[j]=='7'){
flag=1;
break;
}
}
//如果数字含有7或者是7的倍数
if(x[i][m-1]!=0&&(x[i][m-1]%7==0||flag==1)){
b++;
if(b==k){
System.out.println(x[i][m-1]);break;
}
}
}
}
}
问题H
Now, here is a function:
F(x) = 6 * x^7 +8x^6 +7x^3 +5x^2-yx (0 <= x <=100)
Can you find the minimum value when x is between 0 and 100.
解题思路1：
可以用三分查找来实现。首先观察函数的导数h(x)=42x^6 +48x^5 +21x^2+10x-y
(0<=x<=100,y>0),当h(x)>0时，原函数是递增的，当h(x)<0时，原函数是递减的。所以原函数是先递减后递增的，所以函数是凹函数。
三分查找原理：
三分法求单峰（或者单谷）的极值，是二分法的一个简单扩展。
单峰函数和单谷函数如下图，函数f(x)在区间[l, r]内，只有一个极值v，在极值点两边，函数是单调变化的。以单峰函数为例，在v的左边，函数是严格单调递增的，在v右边是严格单调递减的。
下面的讲解都以求单峰极值为例。
如何求单峰函数最大值的近似值？虽然不能直接用二分法，不过，只要稍微变形一下，就能用了。
在[l, r]上任取2个点，mid1和mid2，把函数分成三段。有以下情况：
（1）若f(mid1) < f(mid2)，极值点v一定在mid1的右侧。此时，mid1和mid2要么都在v的左侧，要么分别在v的两侧。如下图所示。
情况（1）：极值点v在mid1右侧
下一步，令l = mid1，区间从[l, r]缩小为[mid1, r]，然后再继续把它分成三段。
（2）同理，若f(mid1) > f(mid2)，极值点v一定在mid2的左侧。如下图所示。下一步，令 r = mid2，区间从[l, r]缩小为[l, mid2]。
不断缩小区间，就能使得区间[l, r]不断逼近v，从而得到近似值。
如何取mid1和mid2？有2种基本方法：
（1）三等分：mid1和mid2为[l, r]的三等分点。那么区间每次可以减少三分之一。
（2）近似三等分：计算[l, r]中间点mid = (l + r) / 2，然让mid1和mid2非常接近mid，例如mid1 = mid - eps，mid2 = mid + eps，其中eps是一个很小的值。那么区间每次可以减少接近一半。
方法（2）比方法（1）要稍微快一点。
(有网友说不要用方法（2）：“因为在有些情况下这个 eps 过小可能导致这两个算出来的相等，如果相等就有可能会判断错方向，所以其实不建议这么写，log3 和 log2 本质上是一样的。”)
注意：单峰函数的左右两边要严格单调，否则，可能在一边有f(mid1) == f(mid2)，导致无法判断如何缩小区间。
参考博客：二分法、三分法
import java.util.Scanner;
public class MainH {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt();
if(T>=1&&T<=100){
for(int i=0;i<T;i++){
double l=0,r=100;
double lmid ;
double rmid ;
double y = scanner.nextDouble();
if(y>0&&y<1000){
while(r-l>1e-7){
lmid = l+(r-l)/3.0;
rmid = r-(r-l)/3.0;
if(val(lmid,y)<val(rmid,y)){
r=rmid;
}else{
l=lmid;
}
}
System.out.println(String.format("%.4f", val(l,y)));
}
}
}
}
private static double val(double x,double y) {
return (6*Math.pow(x, 7)+8*Math.pow(x, 6)+7*Math.pow(x, 3)+5*Math.pow(x,2)-y*x);
}
}
解题思路二：
1.求原函数的导数
2.对导数求零点，当导数等于0时，即为原函数的极值
参考博客：（题解-F(x) = 6 * x ^7 +8x^6 +7x^3 +5x^2-yx）
import java.util.Scanner;
public class MainH1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
double y,h,l,mid = 0;
while(t>0){
y = scanner.nextDouble();
t--;
l = 0.0;
h=100.0;
while(h-l>1e-7){//不断缩小x的范围直到导数无限接近0
mid=(l+h)/2;
if(f(mid,y)<0){
l=mid;
}else{
h=mid;
}
}
System.out.println(String.format("%.4f", F(mid,y)));
}
}
private static double F(double x, double y) {
return 6*Math.pow(x, 7)+8*Math.pow(x, 6)+7*Math.pow(x, 3)+5*Math.pow(x,2)-y*x;
}
//原函数的导数
private static double f(double x,double y) {
return 42*Math.pow(x,6)+48*Math.pow(x,5)+21*Math.pow(x,2)+10*x-y;
}
}