一道数学逻辑题

Question

这是一个朋友年前给我出的题目，一直没做出来。随机生成100个小于100的正整数，得出其平均值(Double类型)，假设这100个数中大于平均值的数的个数为m，小于平均值的数的个数为n，如果(m-n)的绝对值大于1，则从这100个数中去掉一个数，重新计算平均值和m、n，如果(m-n)的绝对值仍大于1，则从这100个数中去掉两个数进行运算。以此类推，直至(m-n)的绝对值不大于1为止(要求在符合此条件时保留尽可能多的数)。最后将这100个随机生成的数写入到int类型的数组i当中，将最终符合要求时所留下的数写入到int类型的数组j当中。新年第一贴，恭祝所有csdn朋友牛年顺利！

Answer 1

感觉像作业？
没做检验import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class Test { private static int counter;

public static void main(String[] args) {

Random random = new Random();
int[] values = new int[100];
//将values中的值放到一个ArrayList中，方便处理，最后再将ArrayList剩下的数放到一个数组中
List<Integer> list = new ArrayList<Integer>();
for(int i = 0; i < values.length; i++) {
values[i] = random.nextInt(100);
list.add(values[i]);
}

//循环检测
while(Math.abs(getM(list) - getN(list)) > 1) {
System.out.println("M: " + getM(list));
System.out.println("N: " + getN(list));
counter++;
System.out.println("Counter：" + counter);
for(int i = 0; i < counter && list.size() > 0; i++) {
list.remove(random.nextInt(list.size()));
}
}

int[] lastValues = new int[list.size()];
for(int i = 0; i < lastValues.length; i++) {
lastValues[i] = list.get(i);
}

System.out.print("初始数组："); 
for(int i : values) {
System.out.print(i + " ");
}
System.out.println();

System.out.print("最后数组：");
for(int i : lastValues) {
System.out.print(i + " ");
}
System.out.println();
}

//求出比平均值大的个数
public static int getM(List<Integer> list) {
int m = 0;
for(int i : list) {
if(i > getAvg(list)) {
m++;
}
}
return m;
}

////求出比平均值小的个数
public static int getN(List<Integer> list) {
int n = 0;
for(int i : list) {
if(i < getAvg(list)) {
n++;
}
}
return n;
}

public static double getAvg(List<Integer> list) {
return (double)getSum(list)/list.size();
}

public static int getSum(List<Integer> list) {
int sum = 0;
for(Integer i : list) {
sum += i;
}
return sum;
}
}

Answer 2

这句list.remove(random.nextInt(list.size()));
随机减去一个数不合理吧。。

Answer 3

随机减去一个数是不行的，因为要求保留尽可能多的数，所以只能一个一个的试。减去一个数时，要挨个减去试；减去两个数时，也要像排列组合一样挨个试，后面的就更复杂了,小弟憋了一个星期实在写不出来，请教csdn各路高手给写一写。

Answer 4

import java.util.*;
public class RandomAverageNum {
private int[] arrayNumAll = new int[100];
private int[] arrayNumAllCopy = new int[100];
private int[] arrayNumRemain;
private int total = 100;
private int m, n = 100;
private int count = 0;
private Random rand;
public RandomAverageNum() {
rand = new Random();
for(int i = 0; i < 100; i++)
arrayNumAll[i] = arrayNumAllCopy[i] = rand.nextInt(99) + 1;
}
public double average() {
double sum = 0.0;
for(int i = 0; i < 100; i++)
sum += arrayNumAll[i];
return sum / total;
}
public void getTheNumWanted() {
while((m - n) > 1 || (n - m) > 1) {
m = 0;
n = 0;
for(int i = 0; i < total; i++) {
if(arrayNumAll[i] > average())
n++;
if(arrayNumAll[i] < average() && arrayNumAll[i] != 0)
m++;
}
total--;
int k;
do {
k = rand.nextInt(100);
}while(arrayNumAll[k] == 0);
arrayNumAll[k] = 0;
}
arrayNumRemain = new int[total];
for(int i = 0, j = 0; i < 100; i++) {
if(arrayNumAll[i] == 0)
continue;
arrayNumRemain[j++] = arrayNumAll[i];
}
}
public void printArray() {
System.out.println("产生的随机数组是：");
for(int i = 0; i < 100; i++) {
System.out.print(arrayNumAllCopy[i] + " ");
if((i +1) % 10 == 0)
System.out.println();
}
System.out.println("剩余的元素构成的数组是：");
for(int i = 0; i < total; i++) {
System.out.print(arrayNumRemain[i] + " ");
if((i + 1) % 10 == 0)
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
RandomAverageNum ran = new RandomAverageNum();
ran.getTheNumWanted();
ran.printArray();
}
}
一个简单的代码哈

Answer 5

如果人品好，有可能第一次|m-n| <= 1；剩下的就是写一个剔除多余的那个数的最快算法。
这种很简单的数学题，要找出最优解，还是要很深的数学能力的啊，哎...

Answer 6

提供一种方法的实现，特别说明：本方法不是最终方案，因为本方法有缺陷，未考虑去掉数时的平均值偏移。import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;/**
 * 随机生成100个小于100的正整数，得出其平均值(Double类型)，
 * 假设这100个数中大于平均值的数的个数为m，小于平均值的数的个数为n，
 * 如果(m-n)的绝对值大于1，则从这100个数中去掉一个数，
 * 重新计算平均值和m、n，如果(m-n)的绝对值仍大于1，则从这100个数中去掉两个数进行运算。
 * 以此类推，直至(m-n)的绝对值不大于1为止
 * (要求在符合此条件时保留尽可能多的数)。
 * 最后将这100个随机生成的数写入到int类型的数组i当中，将最终符合要求时所留下的数写入到int类型的数组j当中。 
 * http://topic.csdn.net/u/20090101/11/4d7e587a-0360-4968-8c46-ac2ef6012dc7.html
 * 
 * 解题思路：
 * 先把这100个数排序，可以从平均数的分界线把数组分为2个数组－大于平均数的m和小于等于平均数的n
 * x[m+n] ..... x[n+1](此次为平均数）x[n]...x[1]
 * 去掉数有2种最优方案，
 * 一种是从n中去掉最小的（减掉小于平均数的小数会让平均数增大，但减掉最小的小数对平均数增大的贡献最大），
 * 另一种是从m中去掉最小的（减掉大于平均数的大数会导致平均数下降，但减掉最小的大数对平均数的下降最小）
 * 所以可以用这2种方案做尝试。
 * 假设减掉1个数，我们可以考虑减掉n中最小的1个，或者m中最小的一个
 * 假设减掉2个数，可以考虑[0,2],[1,1],[2,0]这3种方案。
 */
public class TestMN {
static final int SIZE=100;
static final Random random=new Random();
static final int MAX=99;

private static List<int[]> split(int count){
List<int[]> t=new ArrayList<int[]>();
for (int i=0;i<=count;i++){
int[] temp=new int[2];
temp[0]=i;
temp[1]=count-i;
t.add(temp);
}

return t;
}

private static int[] newArr(int[] src,int n,int[] split){
int[] arr=new int[src.length-split[0]-split[1]];

int count=0;
for (int i=split[0];i<n;i++){
arr[count++]=src[i];
}
for (int i=n+split[1];i<src.length;i++){
arr[count++]=src[i];
}

return arr;

}
public static void printArray(int arr[]){
for (int i=0;i<arr.length;i++){
System.out.print(arr[i]+((i<arr.length)?",":""));
}
System.out.println();
}

private static int lessThan(int[] arr,double avg){
int i=0;
for (;i<arr.length;i++){
if (arr[i]>avg)
break;
}
return i;
}

private static double avg(int[] arr){
double sum=0.0;
for (int i=0;i<arr.length;i++){
sum+=arr[i];
}
return sum/arr.length;
}

public static int[] createArray(){
int[] temp=new int[SIZE];

for (int i=0;i<SIZE;i++){
temp[i]=random.nextInt(MAX)+1;
}
return temp;
} private static boolean testArr(int arr[]){
double avg=avg(arr);
int less=lessThan(arr,avg);
System.out.println("平均值="+avg+"\tm="+(arr.length-less)+"\tn="+less);
if ((arr.length-less)<=less){
return true;
} else {
return false;
}
}

/**
 * 处理数组的主方法
 */
private static int[] process(int arr[]){
//先测试原数组
double avg=avg(arr);
int less=lessThan(arr,avg);
System.out.println("平均值="+avg+"\tm="+(arr.length-less)+"\tn="+less);
//如果数组满足条件则直接返回
if ((arr.length-less)<=less){
return arr;
}
//去掉数组中的一些数－－从1个开始，依次测试
for (int i=1;i<100;i++){
//去掉数的分割方法，比如1可以分割[0,1]和[1,0]，2可以分割成[0,2],[1,1],[2,0]
//这2个数表示分别从n中去掉的个数和从m中去掉的个数
//比如[2,2]，表示从n中去掉最小的2个数并且从m中去掉最小的2个数
List<int[]> temp=split(i);
for (int[] t:temp){
System.out.println("从n中去掉："+t[0]+"个，从m中去掉:"+t[1]+"个");
int[] newArr=newArr(arr,less,t);
//printArray(newArr);
if (testArr(newArr)){
return newArr;
}
}
}
return arr;
}

public static void main(String[] args) {
//产生随机数组
int[] i=createArray();
//处理之前必须先排序
Arrays.sort(i);
//处理数组
int[] j=process(i);
//打印数组
printArray(i);
printArray(j);
}}

Answer 7

16楼高手写的很完美了，算法很漂亮，split方法真是牛！长见识了呵呵
不过还是有点小问题，我把这道题目改了一下，改为10个正整数，然后写了一个穷举法，对比了一下两个写法的结果看出来的。
2楼和8楼还需要进一步研究一下。
如果大家对这道题没兴趣了明天我就要结贴啦。

Answer 8

把100个随机整数保存在一个集合中，先从大到小排序，计算总和，记录个数。
然后计算平均数（整数还是小数？），再计算超过平均数的数据个数m与小于平均数的数据个数n。
如果m-n绝对值为0或者1就ok了，否则就……还没有想好如何处理。甚至有可能出现这样的情况：大于平均数的多了，但是把小的去掉一个，平均数就大了，这样大于平均数的反而少了。

Answer 9

package test;public class RandomNumber { /**
 * 随机生成100个小于100的正整数，得出其平均值(Double类型)，
 * 假设这100个数中大于平均值的数的个数为m，小于平均值的数的个数为n，
 * 如果 (m-n)的绝对值大于1，则从这100个数中去掉一个数，重新计算平均值和m、n，
 * 如果(m-n)的绝对值仍大于1，则从这100个数中去掉两个数进行运算。
 * 以此类推，直至(m-n)的绝对值不大于1为止(要求在符合此条件时保留尽可能多的数)。
 * 最后将这100个随机生成的数写入到int类型的数组i当中，
 * 将最终符合要求时所留下的数写入到int类型的数组j当中。
 * @param args
 */
public static void main(String[] args) {
RandomNumber ran  = new RandomNumber();
int[] originals  = ran.getOriginalArray();
int[] i = new int[100];

int iIndex = 0;
while(true){
double average  = ran.getAverage(originals);
int maxNumber = ran.getMaxNubmer(originals, average);
int minNumber = ran.getMinNumber(originals, average);

if(Math.abs(maxNumber - minNumber) > 1){
int removeNumber = ran.getFollowAverage(originals, average);
originals = ran.remove(originals, removeNumber);
i[iIndex] = removeNumber;
iIndex++;
}else{
break;
}
} System.out.print("remove size = ");
for(Integer in : i){
if(in == 0){
break;
}
System.out.print(in+"\t");
}
System.out.println();
System.arraycopy(originals, 0, i, i.length-originals.length, originals.length);
System.out.print("Original number = ");
for(Integer in : i){
System.out.print(in+"\t");
}
int[] j = originals; System.out.print("\nremianing size = "+originals.length+" numbers = ");
for(Integer in : j){
if(in == 0){
break;
}
System.out.print(in+"\t");
}

} public int getFollowAverage(int[] arr,double avg){ int result = 0;
double min = 1000d;
for(int i = 0 ; i <arr.length ; i++){
double tmp = Math.abs(arr[i]-avg);
if(tmp < min ){
min = tmp;
result = arr[i];
}
}
return result;
}

public int randomNubmer(){
int num = (int)(Math.random()*101);
return num;
}

public int[] getOriginalArray(){
int[] originals = new int[100];
for(int i = 0 ; i < 100 ; i++){
originals[i] = this.randomNubmer();
}
return originals;
}

public double getAverage(int[] arr){
int total  = 0;
int length = arr.length;
for( int i = 0 ; i < length ; i++){
total += arr[i];
}
double result = total/length;
return result;
}

public int getMaxNubmer(int[] arr,double num){
int count = 0;
for(int i = 0 ; i < arr.length ; i++){
if(arr[i] > num){
count ++;
}
}
return count;
}

public int getMinNumber(int[] arr,double num){
int count = 0;
for(int i = 0 ; i < arr.length ; i++){
if(arr[i] < num){
count ++;
}
}
return count;
}

public int[] remove(int[] arr,int number){

int index = 0;
for(int j = 0 ; j < arr.length ; j++ ){
if(number == arr[j]){
index = j;
break;
}
}
for(int i = index ; i < arr.length - 1 ; i++){
arr[i] = arr[i+1];
}
int[] results = new int[arr.length - 1];
System.arraycopy(arr, 0, results, 0, arr.length-1);
return results;
}
}自己写的,运行还可以但是在效率上,不知道哪位有更好的方法