|
[Original]
[Print]
[Top]
|
int a[n]={...}; // a[i]>= 0 && a[i]<n && n<10
int b[n]={...}; // b[0] = 0
其中a中各元素均不相等，b[i]为在a中a[0]到a[i-1]中小于a[i]的元素个数，
eg:
a[5]={0,1,2,3,4,} 则 b[5]={0,1,2,3,4,}
a[5]={4,3,2,1,0,} 则 b[5]={0,0,0,0,0,}
现已知b[n]，欲求a[n]
|
|
----
july is hot.
|
|
[Original]
[Print]
[Top]
|
|
[Original]
[Print]
[Top]
|
找到两个极值的规律:
1. b[n]中找到极小值0且i是最大偏移时b[i]==0，则a[i]==0；
...如b[5]={0,1,0,2,2}则a[2]=0
2. b[n]中找到极大值b[j],则 a[j] == b[j]+(n-1)-j；
...如b[5]={0,1,0,2,2}则a[3]==2+(5-1)-3==3;a[4]==2+(5-1)-4==2
只找出两个值来。。。
|
|
----
july is hot.
|
|
[Original]
[Print]
[Top]
|
|
[Original]
[Print]
[Top]
|
从k=1 开始
如果b[k] > b [k-1] 则 k++
如果b[k] = b [k-1] 则交换，一直到b[k]不能再向前（0的方向）为止。
如果b[k] < b[k-1] , 交换，同时b[k] -- , b[k-1] ++ ,同样让b[k]不能再向前（0的方向）为止。
描述的不太好（poor ),看个事例图吧
b[n] = {0, 1, 0, 2, 2}
0 1 0 2 2
a b c d e
^
0 1 0 2 2
a b c d e
^
0 -1 2 2 2
a c b d e
-2 1 2 2 2
c a b d e
^
-2 1 2 2 2
c a d b e
^
-2 1 2 2 2
c a d e b
-2 1 2 2 2
c a e d b
So c = 0 a =1 e = 2 d=3 b =4
a[] = { 1 4 0 3 2}
|
|
|
[Original]
[Print]
[Top]
|
|
[Original]
[Print]
[Top]
|
好的, 其实问题的本质就是个插入排序。
如果b[k] > b[k-1] 那么a[k] 也是大于a[k-1]的
否则那么a[k] 是小于a[k-1]的(没有相同的), 交换后那么b[k-1] 就因该+1.
那么上面的算法就可以简化了.
|
|
[Original]
[Print]
[Top]
|
|
[Original]
[Print]
[Top]
|
嗯，已知b[]则一定可以对a[]进行排序。
证明：
如果已知b[i]，且a[0],a[1],...,a[i-1]可以排序，那么a[0],a[1],...,a[i]也可以排序。而a[0]是可以排序的，且b[1]已知，数学归纳法，结论可证。
|
|
----
Wir müssen wissen. Wir werden wissen.
|
|
[Original]
[Print]
[Top]
|
|
[Original]
[Print]
[Top]
|
根据mlion的算法写的，只是b[5]={0,1,0,2,2}时译码a[5]正确,可b[5]={0,0,2,2,1}时却不对。
麻烦大家看看阿。
#include <stdio.h>
void swap( int *p1, int *p2 )
{
int temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
}
main()
{
int a[5]={1,4,0,3,2};
int b[5]={0,1,0,2,2};
int c[5]={0,1,2,3,4};
int d[5]={0,1,2,3,4};
int k = 1, i, j, *p1 = b, *p2 = c;
while( k < 5 )
{
/*如果b[k] > b [k-1] 则 k++ */
if( b[k] > b[k-1] ) ++k;
/*如果b[k] = b [k-1] 则交换，一直到b[k]不能再向前（0的方向）为止。 */
else if( b[k] == b[k-1] )
{
i = k;
for( i; i>0; --i )
{
if( b[i] == b[i-1] )
{
swap( p2+i, p2+i-1 );
}
}
++ k;
}
/*如果b[k] < b[k-1] , 交换，同时b[k] -- , b[k-1] ++ ,同样让b[k]不能再向前（0的方向）为止。 */
else if( b[k] < b[k-1] )
{
j = k;
for( j; j>0; --j )
{
if( b[j] < b[j-1] )
{
++ b[j-1];
-- b[j];
swap( p1+j, p1+j-1 );
swap( p2+j, p2+j-1 );
}
}
++ k;
}
}
k=0;
for( k; k<5; ++k )
{
a[c[k]] = d[k]; /*So c = 0 a =1 e = 2 d=3 b =4 */
}
k=0;
for( k; k<5; ++k )
{
printf(" %d ", a[k]);
} printf("
");
}
大家有其他的算法么？
|
|
|
----
july is hot.
|
|
[Original]
[Print]
[Top]
|
|
[Original]
[Print]
[Top]
|
int a[5] = {0, 1, 2, 3, 4};
int c[5];
bool check_b_is_valid(int * b , int len)
{
int i = 0;
if (len <= 0)
return false;
for (i=0; i<len; i++)
if (b[i]>i || b[i] < 0)
return false;
return true;
}
void get_a_from_b(int * b, int len)
{
int i, j, tmp, tmp2;
if (check_b_is_valid(b, len)) {
for(i=1; i<len; i++) {
tmp = b[i];
tmp2 = a[i];
j=i-1;
while(j >= 0 && b[j] >= tmp) {
b[j+1] = b[j] + 1;
a[j+1] = a[j];
j--;
}
b[j+1] = tmp;
a[j+1] = tmp2;
}
for (i=0; i<len; i++)
c[a[i]] = i;
for (i=0; i<len; i++)
printf("%d ", c[i]);
printf("
");
}
else
printf("b is illegal
");
}
int main()
{
int b[5] = {0, 0, 2, 2, 1};
int i;
for (i=0; i<5; i++)
printf("%d ", b[i]);
printf("
");
get_a_from_b(b , 5);
return 0;
}
|
|
|
[Original]
[Print]
[Top]
|
|
[Original]
[Print]
[Top]
|
for(i=1; i<len; i++) {
tmp = b[i];
tmp2 = a[i];
j=i-1;
while(j >= 0 && b[j] >= tmp) {
b[j+1] = b[j] + 1;
a[j+1] = a[j];
j--;
}
b[j+1] = tmp;
a[j+1] = tmp2;
}
========================================
多谢mlion帮忙。
|
|
|
----
july is hot.
|
|
[Original]
[Print]
[Top]
|
|
[Original]
[Print]
[Top]
|
/*
* 解题思路：
* 由b[i]中的元素，从b[1] .... b[i]逐个分析，得出a[0] ... a[i]从小到大的顺序，结果不唯一。
* 还需改进一不可能的情况。
*/
#include <stdio.h>
#define LEN 5
struct link {
int index;
struct link *next;
};
struct link *gen_sort(int b[], int n)
{
int i, j;
struct link *head, *ptr, *tmp;
struct link top;
if (b[0] != 0) {
return NULL;
} else {
head = (struct link *)malloc(sizeof(struct link));
head->index = 0;
head->next = NULL;
}
top.next = head;
for (i = 1; i < n; i++) {
print_sort(top.next);
if (b[i] > i) {
free_sort(head);
return NULL;
}
ptr = ⊤
for (j = 0; j < b[i] ; j++) {
ptr = ptr->next;
}
tmp = ptr->next;
ptr->next = (struct link *)malloc(sizeof(struct link));
ptr->next->index = i;
ptr->next->next = tmp;
}
return top.next;
}
free_sort(struct link *sort)
{
struct link *ptr;
for (ptr = sort; ptr != NULL; ptr = ptr->next) {
free(ptr);
}
}
print_sort(struct link *sort)
{
struct link *ptr;
for (ptr = sort; ptr != NULL; ptr = ptr->next) {
printf("%d ", ptr->index);
}
printf("
");
}
int main()
{
int b[LEN] = {0, 0, 2, 2, 1};
struct link *sort;
sort = gen_sort(b, LEN);
if (!sort) {
printf("impossible
");
return 0;
}
free_sort(sort);
return 0;
}
|
|
|
[Original]
[Print]
[Top]
|
|
声明: 本页内容为中国Linux论坛的内容镜像，文章的版权以及其他所有的相关权利属于中国Linux论坛和相应文章的作者，如果转载，请注明文章来源及相关版权信息。
