一道算法题（初中生的）

Question

设有一个数组A:ARRAY[0..N-1] OF INTEGER；数组中存放的元素为0～N-1之间的整数，且A[i]≠A[j]（当i≠j时）。
   例如：N=6时，有：                   A=（4，3，0，5，1，2）
       此时，数组A的编码定义如下：
       A[0]的编码为0；
       A[i]的编码为：在A[0]，A[1]，……A[i-1]中比A[i]的值小的个数（i=1，2……N-1）
    ∴上面数组A的编码为： B=（0，0，0，3，1，2）
    程序要求解决以下问题：
①给出数组A后，求出其编码；
②给出数组A的编码后，求出A中的原数据。

Answer 1

int[] arrayToCode(int[] arg) {
     if(arg.length == 1)
          return new int[]{0};     int[] ret = new int[arg.length]; 
     ret[0] = 0;
     int count = 0;
     for(int i = 1; i < arg.length; i++) {
          for(int j = 0; j < i; j++) {
               if(arg[j] < arg[i]) {
                    count++;
               }
          }
          ret[i] = count;
          count = 0;
     }
     return ret;
}

Answer 2

import java.util.ArrayList;
import java.util.List;public class Test{

public static void main(String [] args){
//源码
   int[] A={4,3,0,5,1,2};
   List<Integer> listA=new ArrayList<Integer>();
   for(int i=0;i<A.length;i++)
   {
   int count=0;
   for(int j=0;j<i;j++)
   {
   if(A[i]>A[j]){
   count++;
   }
   }
   listA.add(count);
   }
   //输出编码
   System.out.println(listA.toString());
}
}

Answer 3

A[i]的编码为：在A[0]，A[1]，……A[i-1]中比A[i]的值小的个数（i=1，2……N-1）
    ∴上面数组A的编码为： B=（0，0，0，3，1，2） 
 这句没理解。。
  请高手解答

Answer 4

public class TestArr { public static void main(String args[]){
int a[] = {4,3,0,5,1,2};
arr(a);
}

public static void arr(int a[]){
int count = 0;
for(int i = 0; i < a.length; i++){
if(i == 0)
System.out.print(0);
else{
for(int j = 0; j <= i-1; j++){
if(a[i] > a[j])
count++;
}
System.out.print(" "+count);
}
count = 0;
}
}
}
\
以上程序是第一问，第二问有问题吧，第二问的结果不确定啊，可能性很多

Answer 5

A:ARRAY[0..N-1] 这里方括号表示的是数组大小吧，B(0)的话，A也只有一个0了

Answer 6

import java.util.*;
import java.text.*;
public class Test{ 
//public static Timer t=new Timer();
    public static void main(String args[]) throws Exception {
     int[] a=new int[10];
     for(int i=0;i<a.length;i++){
     a[i]=i;
     }
     shuffArray(a);
     System.out.println("原数据：");
     System.out.println(Arrays.toString(a));
     System.out.println("\n数组编码：");
     int[] b=codeArray(a);
     System.out.println(Arrays.toString(b));
     System.out.println("\n根据编码复原数组：");
     int[] c=decodeArray(b);
     System.out.println(Arrays.toString(c));
  
    }
    
    //对数组编码:
    //
    public static int[] codeArray(int[] a){
     int[] result=new int[a.length];
     for(int i=0;i<result.length;i++){
     int count=0;
     for(int j=0;j<i;j++){
     if(a[j]<a[i]){
     count++;
     }
     }
     result[i]=count;
     }
     return result;
    }
    
    //根据编码，得出原数组：
    //
    public static int[] decodeArray(int [] b){
     int[] result=new int[b.length];
     ArrayList<Integer> temp=new ArrayList<Integer>();
     for(int i=0;i<b.length;i++){
     temp.add(i);
     }
     for(int i=b.length-1;i>=0;i--){
     result[i]=temp.get(b[i]);
     temp.remove(b[i]);
     }
     return result;
    }
    
    //打乱数级的顺序：
    //
public static void shuffArray(int[] arr){
Random rand=new Random();
for(int i=arr.length-1;i>0;i--){
int tempIndex=rand.nextInt(i);
int temp=arr[i];
arr[i]=arr[tempIndex];
arr[tempIndex]=temp;
}
}
 
}一次运行结果如下:
F:\java>java Test
原数据：
[9, 0, 7, 8, 3, 4, 2, 1, 6, 5]数组编码：
[0, 0, 1, 2, 1, 2, 1, 1, 5, 5]根据编码复原数组：
[9, 0, 7, 8, 3, 4, 2, 1, 6, 5]

Answer 7

A:ARRAY[0..N-1] 这里方括号表示的是数组大小吧，B(0)的话，A也只有一个0了 
你没读懂题目吧，
A[0]的编码为0
也就是A[0]不管是什么数，它的编码结果都是0，
A={1|2|3|4....n} 编码结果都是 B={0}.
那 B={0} 能推出一个唯一的值吗？

Answer 8

设有一个数组A:ARRAY[0..N-1] OF INTEGER；数组中存放的元素为0～N-1之间的整数
只有一个数 那只能是0了

Answer 9

这道题是，NOI（全国青少年信息学奥林匹克竞赛）在1995年的复赛试题，初中组的。

Answer 10

以下是测试数据，测试一下各位的程序对不对：①由数组求编码：
a 输入：N=6  A=（0，1，2，3，4，5）
  输出：  B=（0，1，2，3，4，5）b 输入：N=6  A=（5，4，3，2，1，0）
  输出：  B=（0，0，0，0，0，0）c 输入：N=8  A=（1，0，3，2，5，4，7，6）
  输出：  B=（0，0，2，2，4，4，6，6）
    
②由编码求原数组：
a 输入：N=5  B=（0，0，0，0，0）
  输出：  A=（4，3，2，1，0）b 输入：N=10  B=（0，1，2，3，4，5，6，7，8，9）
  输出：   A=（0，1，2，3，4，5，6，7，8，9）c 输入：N=7   B=（0，0，0，0，4，5，6）
  输出：   A=（3，2，1，0，4，5，6）

Answer 11

/**
 * @param args
 */
public static void main(String[] args) {
int[] a = {4, 3, 0, 5, 1, 2};
int[] b = encode(a);
for(int i : b){
System.out.print(i+" ");
}

System.out.println("\n#######################################");
b = new int[]{0, 0, 0, 3, 1, 2};
a = decode(b);
for(int i : a){
System.out.print(i+" ");
}
}

private static int[] encode(int[] array){
int[] result = new int[array.length];
result[0] = 0;

for(int i=1; i<array.length; i++){
result[i] = getCount(array, i);
}

return result;
}

private static int getCount(int[] array, int i){
int count = 0;
for(int j=0; j<i; j++){
if(array[j]<array[i]){
count++;
}
}
return count;
}

private static int[] decode(int[] array){
int[] result = new int[array.length];
result[array.length - 1] = array[array.length - 1];

List<Integer> list = new LinkedList<Integer>();
for(int i=0; i<array.length; i++){
list.add(i); //全部添加到数组中
}
list.remove(Integer.valueOf(array[array.length - 1])); //去掉最后一个

for(int i=array.length-2; i>=0; i--){
result[i] = list.get(array[i]);
list.remove(array[i]);
}

return result;
}

Answer 12

第二问一点思路不知道内存这么样：
原码为从小到大的数组；
1 从右边向左开始找，出现第一个“0”的位置为最小数，将最小数赋值给它；
2 以上面找到的“0”位置为基准，往右找是否存在“1”，若存在则“1”的位置为第二小数，并以找到的“1”位置为基准；
else则往左找第一个为“0”的位置为第二小的数，并以它为基准，向右继续找“1”，不存在继续向左找“0”；

Answer 13

第一小题比较简单，第二题：设int[] a = {0, 1, 2, 3, 4, 5};
给定的编码 B=（0，0，0，3，1，2）从最后一个往前求解。
1、B[5] = 2; 则A[5] = a[2] = 2; 去除a数组中a[2]这个元素得a = {0, 1, 3, 4, 5}
2、B[4] = 1; 则A[4] = a[1] = 1; 去除a数组中a[1]这个元素得a = {0, 3, 4, 5}
3、重复以上步骤得A[3] = a[3] = 5; a = {0, 3, 4}
               A[2] = a[0] = 0; a = {3, 4}
               A[1] = a[0] = 3; a = {4}
               A[0] = a[0] = 4; a = {}
4、最终得到：A = (4, 3, 0, 5, 1, 2)对于不同的n思路同上