1、百钱百鸡、千钱千鸡、万钱万鸡的二重、三重循环求解,并计时。 根据所给的数据,分别对前100、前1000及全部数据分别使用冒泡排序和Java的Qsort进行排序,并计时
时间: 2024-09-08 11:03:56 浏览: 149
首先,我们来解释一下"百钱百鸡"问题,这是一道经典的数学问题,也被称为"百钱买百鸡"。问题的内容是:公鸡每只5钱,母鸡每只3钱,小鸡3只1钱,现在用100钱买100只鸡,问公鸡、母鸡、小鸡各有多少只?
解这类问题通常会用到穷举法,也就是二重或三重循环来遍历所有可能的组合,找到满足条件的解。下面是使用Java实现的示例代码:
```java
public class HundredChickens {
public static void main(String[] args) {
int money = 100; // 总钱数
int count = 100; // 总鸡数
int start = System.currentTimeMillis(); // 记录开始时间
// 二重循环求解
for (int cock = 0; cock <= count / 5; cock++) { // 公鸡最多可以买20只
for (int hen = 0; hen <= count / 3; hen++) { // 母鸡最多可以买33只
int chicks = count - cock - hen; // 剩下的钱都买小鸡
if (chicks % 3 == 0 && (cock * 5 + hen * 3 + chicks / 3) == money) {
System.out.println("公鸡:" + cock + "只,母鸡:" + hen + "只,小鸡:" + chicks + "只");
}
}
}
long endTime = System.currentTimeMillis(); // 记录结束时间
System.out.println("二重循环计算用时:" + (endTime - start) + "毫秒");
// 三重循环类似,但在此不再赘述
}
}
```
接下来,我们来看排序部分。使用冒泡排序和Java自带的Arrays.sort()(它底层实现可能是快速排序或其他高效的排序算法)进行排序,并记录时间。以下是Java实现的示例代码:
```java
import java.util.Arrays;
import java.util.Random;
public class SortTest {
public static void main(String[] args) {
int[] array = new int[100]; // 前100个数据
int[] array1000 = new int[1000]; // 前1000个数据
int[] arrayFull = new int[10000]; // 全部数据,这里假设为10000个数据
Random random = new Random();
// 初始化数据
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt(100);
array1000[i] = random.nextInt(1000);
arrayFull[i] = random.nextInt(10000);
}
// 冒泡排序前100个数据并计时
long start = System.currentTimeMillis();
bubbleSort(array);
long end = System.currentTimeMillis();
System.out.println("冒泡排序前100个数据用时:" + (end - start) + "毫秒");
// Arrays.sort()排序前1000个数据并计时
start = System.currentTimeMillis();
Arrays.sort(array1000);
end = System.currentTimeMillis();
System.out.println("Arrays.sort()前1000个数据用时:" + (end - start) + "毫秒");
// Arrays.sort()排序全部数据并计时
start = System.currentTimeMillis();
Arrays.sort(arrayFull);
end = System.currentTimeMillis();
System.out.println("Arrays.sort()全部数据用时:" + (end - start) + "毫秒");
}
// 冒泡排序的实现
private static void bubbleSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
}
```
注意:冒泡排序的时间复杂度是O(n^2),所以对于大数据量排序效率不高;而Arrays.sort()使用的排序算法根据数据情况不同可能是不同的,通常情况下是快速排序、归并排序或TimSort(Java 7引入的排序算法),其时间复杂度通常是O(n log n)。
阅读全文