研究生复试的算法,求解

挨踢民工的乐章 2011-04-05 01:52:08

给你一个二进制序列比如10100
进行左循环移位n 次,n是二进制序列的长度
每移位一次产生一个新二进制序列

序列1
10100
01001
10010
00101
01010

然后把这些序列进行排序,变成序列2

序列2

00101
01001
01010
10010
10100

提取最后一列(注意是列不是行):11000

然后题目的意思是,给你最后一列11000,让我们推出序列2的第一行

求算法..

...全文

2345 96 打赏收藏转发到动态举报

写回复

用AI写文章

96 条回复

切换为时间正序

请发表友善的回复…

发表回复

showjim 2011-04-15

打赏
举报

去掉一个跳转

        private static string fristRow(string lastCol)

        {

            int index0 = lastCol.Length;

            int[] link = new int[index0];

            foreach (char c in lastCol) index0 -= c & 1;

            for (int index1 = lastCol.Length, index = lastCol.Length - 1; index >= 0; --index)

            {

                link[lastCol[index] == '0' ? --index0 : --index1] = index;

            }

            char[] value = new char[lastCol.Length];

            index0 = link[0];

            for (int end = lastCol.Length, index = 0; index != end; ++index, index0 = link[index0])

            {

                value[index] = lastCol[index0];

            }

            return new string(value);

        }

showjim 2011-04-15

打赏
举报

写了个O(n)的程序

        private static string fristRow(string lastCol)

        {

            int index0 = lastCol.Length;

            int[] link = new int[index0];

            foreach (char c in lastCol)

            {

                if (c == '1') --index0;

            }

            for (int index1 = lastCol.Length, index = lastCol.Length - 1; index >= 0; --index)

            {

                link[lastCol[index] == '0' ? --index0 : --index1] = index;

            }

            char[] value = new char[lastCol.Length];

            index0 = link[0];

            for (int end = lastCol.Length, index = 0; index != end; ++index, index0 = link[index0])

            {

                value[index] = lastCol[index0];

            }

            return new string(value);

        }

liyzgmail 2011-04-14

打赏
举报



#include <stdio.h>



/* 定义序列位数 */

#define LEN 5 



/* 简单的排序

 * 序列1 --> 序列2*/

static void sort(size_t *array, size_t len)

{

	size_t i, j;

	size_t dst,tmp;



	for (i = 0; i < len; i++) {

		dst = i;

		for (j = i+1; j < len; j++) {

		  if ( array[dst] > array[j]) {

						dst = j;

			}

		}



		if (dst != i) {

			tmp = array[i];

			array[i] = array[dst];

			array[dst] = tmp;

		}



	}

}



/* 验证序列是否正确

 * @dst，为目标序列，如二进制 11000 */

static size_t check(size_t *array, size_t len, size_t dst)

{

		size_t num = 0;

		size_t i;



		for (i = 0; i < len; i++) {

			num = (num << 1) | (array[i] & 1);

		}



		return (num == dst);

}



/* 更新序列1 */

static void update(size_t *array, size_t len, size_t new)

{

		size_t i = 0;

	  for (i = 0; i < len - 1; i++) {

			array[i] = array[i+1];

		}

		array[len-1] = new;

}



static void __printf(size_t num)

{

		size_t i = 0;

		size_t bit = 0;



		for (i = 0; i < LEN; i++) {

			bit = (num & (1 << (LEN - i - 1))) >> (LEN - i - 1);

			printf("%d", bit);

		}

}



int main()

{

	size_t a = 0x14; /* 起始二进制 10100*/



	size_t i = 0; 



	size_t dst = 0x18; /* 比对序列 11000 */

	

	size_t array[LEN] = {0};

	

	while (1){

		/* 对序列移位操作*/

		a =	((~(1 << (LEN -1)) & a) << 1) | ((a & (1 << (LEN-1))) >> (LEN -1));



		if (i < LEN) { 

					/* 初始化序列1*/

					array[i++] = a;

		} else {

					/* 排序，得到序列2，然后校对 */

					sort(array, LEN);

					if (check(array, LEN, dst)) {

									__printf(array[0]);

									printf(" 是你要找的序列\n");

								  break;

					} else {

							update(array, LEN, a);

					}

					

		}

	}

	

	/* 打印出序列2 */

	printf("序列2： \n");

	for (i = 0; i < LEN; i++) {

		__printf(array[i]);

		printf("\n");

	}

	printf("\n");

	

	return 0;

}

编译
$ gcc test.c -o test
测试
$ ./test

00101 是你要找的序列
序列2：
00101
01001
01010
10010
10100

这是完整的源码，看不懂就没有办法了。

yoxibaga 2011-04-13

打赏
举报

这个算法，主要是，找出某个序列是有那个序列移位而来的。
第一步：很显然，seq2第一列应该是00……11递增的。
第二步:右移一位（显然右移一位所得的序列也是seq2中的序列，只不过无序）
第三部:找出右移后最小的数（最开始其实是开头的两位二进制的比较，若遇到相同的，比如在右移位前，存在两个序列为0……1,0……1.，右移后开头的二序列为10……，10……，因为后面的数位同右移前是一样的，所以前者小于后者，这样就找到最小的序列，也能得到，这个序列其实就是seq2中第一个序列左移的结果。这样就找到一组对应的关系，并可以填充一位）
重复第三步，找到第二小的，直到能够填充所有数位，或者找到所有的对应关系。

挨踢民工的乐章 2011-04-12

打赏
举报

[Quote=引用 90 楼 liyzgmail 的回复:]

其中，原序列左移位的次数未知，也就是序列1未知，最后的序列2也是未知的。
我的程序就是最基本代码实现实现，代码没有优化过。
可以把我的代码扩充到小于等于32位序列，只要改其中的关于位数的5，和4两个数，最好定义一个LEN，让它代表长度
[/Quote]

你define 一个位数多好，能不能说下你的思路。。？？

liyzgmail 2011-04-11

打赏
举报

其中，原序列左移位的次数未知，也就是序列1未知，最后的序列2也是未知的。
我的程序就是最基本代码实现实现，代码没有优化过。
可以把我的代码扩充到小于等于32位序列，只要改其中的关于位数的5，和4两个数，最好定义一个LEN，让它代表长度

liyzgmail 2011-04-11

打赏
举报

上面的是我写的，测试通过，不知道是否符合楼主的意思。

liyzgmail 2011-04-11

打赏
举报

#include <stdio.h>
/* 简单的排序
* 序列1 --> 序列2*/
static void sort(size_t *array, size_t len)
{
size_t i, j;
size_t dst,tmp;

for (i = 0; i < len; i++) {
dst = i;
for (j = i+1; j < len; j++) {
if ( array[dst] > array[j]) {
dst = j;
}
}

if (dst != i) {
tmp = array[i];
array[i] = array[dst];
array[dst] = tmp;
}

}
}

/* 验证序列是否正确
* @dst，为目标序列，如二进制 11000 */
static size_t check(size_t *array, size_t len, size_t dst)
{
size_t num = 0;
size_t i;

for (i = 0; i < len; i++) {
num = (num << 1) | (array[i] & 1);
}

return (num == dst);
}

/* 更新序列2 */
static void change(size_t *array, size_t len, size_t new)
{
size_t i = 0;
for (i = 0; i < len - 1; i++) {
array[i] = array[i+1];
}
array[len-1] = new;
}

int main()
{
size_t a = 0x14; /* 起始二进制 10100*/

size_t i;
size_t count = 0;

size_t dst = 0x18; /* 比对序列 11000 */

size_t array[5] = {0};

while (1){
a = (a << 1) & ~(1 << 5) | ((a & (1 << 4)) >> 4);

if (count < 5) {
array[count++] = a;
} else {
sort(array, 5);
if (check(array, 5, dst)) {
printf("%02x 是你要找的序列\n", array[0]);
break;
} else {
change(array, 5, a);
}
}
}

/* 打印出序列2 */
printf("序列2： ");
for (i = 0; i < 5; i++) {
printf("%02x ", array[i]);
}
printf("\n");

return 0;
}

日立奔腾浪潮微软松下联想 2011-04-11

打赏
举报

算法：

假设变换2的最后一列记为L（实现上可以作为1维数组）
1. 建立一个n*n的矩阵M（实现上可以作为2维数组），初始值为全0
2. 将L复制到M的第一列（最左边的一列）
3. 对M的第一列进行排序（从小到大）
4. 循环n-2次{将M的每行右移1位；将L复制到M的第一列；将M按行排序}
5. 将L复到M的最后1列（最右边的一列）
此时的M就是变化2后的矩阵。

日立奔腾浪潮微软松下联想 2011-04-11

打赏
举报

到目前为止，只有
http://topic.csdn.net/u/20110405/13/9393c9a7-b86c-482d-acaf-e8c391541875.html
里32楼redhumor的算法是对的，而且比较快（当然还可以再稍微优化一点）。

竞天问 2011-04-11

打赏
举报

[Quote=引用 83 楼 sl51314240 的回复:]
这道题简单思想就是：
1.找出最后一位是1的集合（10001,00011）
2.从左往右按位比较，找到不同位的地方，把该位为1的扔掉，留0的，直到剩1个
3.这道题的话第一步就比较出来了，两个数左数第一位就不同，把1扔到，剩00011
[/Quote]
因为序列中1的个数是相同的，所以你这第2步其实就是比较大小，取最小的呗

挨踢民工的乐章 2011-04-10

打赏
举报

看有答案没。。。。。。。。。。。。谁给总结下。。

sl51314240 2011-04-10

打赏
举报

时间复杂度O(2n) = O(n)

sl51314240 2011-04-10

打赏
举报

这道题简单思想就是：
1.找出最后一位是1的集合（10001,00011）
2.从左往右按位比较，找到不同位的地方，把该位为1的扔掉，留0的，直到剩1个
3.这道题的话第一步就比较出来了，两个数左数第一位就不同，把1扔到，剩00011

dskit 2011-04-10

打赏
举报

分析下时间复杂度：=构造序列1的复杂度=O(N), N为bit数

dskit 2011-04-10

打赏
举报

1. 确定序列2的最后一位是0还是1，用flag记录
2. 构造序列1，记录最后一位与flag相等，且最小的数min
3. 输出min，即为答案

挨踢民工的乐章 2011-04-10

打赏
举报

版主给加亮下吧。。。。

wjmde678 2011-04-10

打赏
举报

这个可以考虑为AES的解密操作，不过没有具体想明白，提过一个思考路径，可以看看攻击算法里面的东西

竞天问 2011-04-10

打赏
举报

[Quote=引用 77 楼 wenqingshan_hit 的回复:]
好高的楼……http://www.kaidian88.com
[/Quote]

damn you!我以为后边是答案呢，广告啊！

[Quote=引用 76 楼 benben2301 的回复:]
看有答案没。。。。。。。。。。。。谁给总结下。。
[/Quote]
最接近的答案只是说答案不唯一，也没个确定的求法，默哀一下吧