请教一道关于计算机得证明题

kingd

Implementiere Insert-Sort für Listen,beweise die Korrektheit der Implementierung:<br>1. das Resultat der Sortierfunktion ist sortiert<br>2. in der sortierten Liste kommt jede Zahl genauso oft vor wie in der ursprünglichen Liste

kingd

例如<br>往排好序的list里插数<br>insert n [] = n:[]<br>insert n (x:xs)= if n &lt;= x then n:x:xs<br>                                       else x insert n xs)<br><br>排序<br>insertsort [] = []<br>sort x:xs = insert x (insertsort xs)<br><br><br>一个数小于list里的所有元素<br>less n [] = True<br>less n (x:xs) = n &lt;= x &&  less n xs<br><br>list是否被排好序了<br>sorted [] = true<br>sorted (x:xs) = less x xs && sorted xs<br><br>list里有多少个n<br>count n [] = 0<br>count n (x:xs) = if n/=x then count n xs<br>                                     else 1+(count n xs)<br><br>证明  sorted (insertsort l)= true    durch Induktion<br><br>         count n l= count n (insertsort l)  durch Indution<br>