c#编码算法实现
大家好，本人在学习研究一个关于编码算法实现的，由于缺乏编程经验，在此询问如何编程实现此算法．算法描述：
First．输入为长度为偶数Ｎ的二进制的向量Ｖ，如（０１０１００００００１０１０１．．．．．），Ｎ比较大，如１０２４，意思为输入向量长度为１０２４．
Second．对前缀长度b取反,(０＜b=＜Ｎ，)后缀Ｎ－b位不变．使得输入向量Ｖ变为平衡向量．（所谓平衡向量意思是在向量中０的数目和１的数目相等）由此可得到很多平衡向量满足此条件．
Third.对上面的平衡向量的前c位进行计算，（0 <c=N),计算绝对k= (２＊前c位中１的数目)－c
Fourth.由此可知，上面的平衡向量对应有很多k值，比较求出最大的Ｋ值，
由最大K值找到对应的c和对应的b
最后输出(b,c,Ｋ)
不知道，大家有什么具体实现的想法．
一直想学Ｃ＃，所以打算用c#来实现，希望大家给点指点．
问题：
１：如何存这个Ｎ位的二进制向量Ｖ
２：存在很多中间的平衡向量如何存储，
３：这个实际的过程是个逆推的过程k知道了，推出c，和b
--------------------编程问答-------------------- 可以可以采用ArrayList来存储二位向量和所有的平衡向量,然后逆向取之
--------------------编程问答-------------------- 可以可以采用ArrayList来存储二位向量和所有的平衡向量,然后逆向取之
--------------------编程问答--------------------
using System;--------------------编程问答-------------------- 问题：
using System.Collections;
using System.Collections.Generic;
class Vector
{
private BitArray vector;
public Vector(int[] vector)
{
this.vector = new BitArray(vector);
}
public int Second()
{
...
}
public int Third()
{
...
}
public int Fourth()
{
...
}
}
class Test
{
static Vector First(int length)
{
int[] vectorBase = new int[length / 32];
Random r = new Random();
for (int i = 0; i < vectorBase.Length; i++)
vectorBase[i] = r.Next();
return new Vector(vectorBase);
}
static void Main()
{
Vector v = First(1024);
int b =v.Second();
...
...
}
}
１：如何存这个Ｎ位的二进制向量Ｖ
２：存在很多中间的平衡向量如何存储，
３：这个实际的过程是个逆推的过程k知道了，推出c，和b
----------------------------------------------
1. 数组即可, 当然你可以用C#的BitArray, 但那样就不是个通用算法.
2. 楼主有没有接触过"动态规划"算法? 你的问题很适合用动态规划做.
首先我们分析一下你的要求, 你将前b位取反以后, 0和1个数相等. 我们假设在前b位中, 0有x个, 1有y个. 在b+1到n位中, 0有m个, 1有n个.
那么初始状态, 就是前面x个0, y个1, 后面m个0, n个1.
取反个数相等, 即是x+n=m+y, 就是y-x=n-m, 也就是说, 前段的1,0个数之差, 等于后段1,0个数之差. 也就是假设前端1比0多了多少个, 后段1比0也
要多多少个.
那么我们可以构建一个动态规划数组int[] dpArr=new int[n];
dpArr[i]记录到i时, 1比0多的个数, 显然if{arr[i]==1} {dpArr[i]=dpArr[i-1]+1;} else { dpArr[i]=dpArr[i-1];}
这是动态规划的典型特征.
那么, 如何确定"对前缀长度b取反"中的b呢?
其实就是寻找dpArr[i]=dpArr[n-1]/2的i, 等于就是只要1,0差值等于动态规划数组的最后一个值得1/2即可, 原理? 自己想想, 很简单.
这个并不需要你再次遍历dpArr, 最开始的时候, 用一个index记录就可以了.
3. 其实就是找前c位中, 1,0差距最大的子序列, 这个太轻松了... dpArr中, 值最大的那个index就是你要找的k.
--------------------编程问答-------------------- dpArr[i]记录到i时, 1比0多的个数, 显然if{arr[i]==1} {dpArr[i]=dpArr[i-1]+1;} else { dpArr[i]=dpArr[i-1];}
---------------------
不好意思打错了...
应该是
--------------------编程问答-------------------- 谢谢，大家的回答，我自己也写了一个。
//当前是1
if{arr[i]==1}
{
dpArr[i]=dpArr[i-1]+1;
}
else
{
dpArr[i]=dpArr[i-1]-1;
}
第一次用才c#,可能有些漏洞，多多包涵
我是用普通的一维的字符矩阵存的这个2进为向量的
用一个2维的矩阵存可能的的k,然后在这个2纬数组里找出最大的，就是k,2维矩阵的两个下标就是b和c
大家差差阿，有什么错吗？
还有是不知道c#用不用类似于c++的delete的把new分配在heap上的动态空间删除了
怎么删除这些动态生成的矩阵呢〉？？
还有矩阵往函数里传是传参的阿。
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication6
{
class hashencoder
{
public int i;
public int t;
public char Bit;
public int Top;
public char[] Vector;
//initialize the Constructor of hashencoder
public hashencoder(char[] Vector)
{
this.Vector = Vector;
}
//start encoding
public void encoding()
{
calculatehash();
Console.WriteLine("After encoding :");
Console.WriteLine("Hash Value=(i({0}),t({1}),Bit({2});Top({3}))", this.i, this.t,this.Bit,this.Top);
}
// belows reverse the prefix of V from 1 to 0 , vice verse
static char[] reverse(char[] V, int prefix)
{
char[] temp = (char[])V.Clone();
for (int i = 0; i < prefix; i++)
{
if (temp[i] == '1')
temp[i] = '0';
else temp[i] = '1';
}
return temp;
}
//as follows,calculate the weight of the prefix of a vector
static int weight(char[] V, int prefix)
{
int count = 0;
for (int i = 0; i < prefix; i++)
{
if (V[i] == '1')
count++;
}
return count;
}
//as follows,calculate the weight of a vector
static int weight(char[] V)
{
int count = 0;
for (int i = 0; i < V.Length; i++)
{
if (V[i] == '1')
count++;
}
return count;
}
//as follows,display the vector
static void display(char[] V)
{
for (int i = 0; i < V.Length; ++i)
{
Console.Write(V[i]);
}
Console.WriteLine("");
}
// calulate the difference between 0'number and 1' of the l length of vector
static int difference01(int l, char[] V, ref int Bit)
{
Bit = 1;
int result;
result = 2 * weight(V, l) - l;
if (result < 0)
{
Bit = 0;
result = -result;
}
return result;
}
//caculate the biggest of the 2 dimmensional array.
static void findTop(int[,] b, ref int i, ref int t, ref int Top)
{
i = t = 1;
Top = b[1, 1];
for (int k = 1; k < b.GetLength(0); k++)
{
for (int j = 1; j < b.GetLength(1); ++j)
{
if (b[k, j] > Top)
{
Top = b[k, j];
i = k;
t = j;
}
}
}
}
// invert the vector from head to tail
static void invert(char[] V)
{
float n = (float)V.Length / 2 - V.Length / 2;
//if (((float)V.Length / 2 - V.Length/2) == 0)
char temp;
for (int i = 0, j = V.Length - 1; i < V.Length / 2; i++)
{
temp = V[i];
V[i] = V[i + j];
V[i + j] = temp;
j = j - 2;
}
}
//calculate the xor
static int xor1(int bit)
{
if (bit == 0)
bit = 1;
else
bit = 0;
return bit;
}
//transfer int to char
static char transterInttoChar(int i)
{
char c;
c = (i == 0 ? '0' : '1');
return c;
}
// calculate the hash value
private void calculatehash()
{
char[] V = this.Vector;
int[,] temp = new int[V.Length + 1, V.Length + 1];
int[,] bit = new int[V.Length + 1, V.Length + 1];
// int[][] temp = new int [V.Length][];
//int[][] bit = new int [V.Length][];
char[] tempV=new char[V.Length];
for (int i = 1; i <= V.Length; i++)
{
tempV = reverse(V, i);
//temp[i] = new int[V.Length];
//bit[i] = new int[V.Length];
int w = weight(tempV);
for (int j = 1; j <= V.Length; j++)
{
if (w == V.Length / 2)
temp[i, j] = difference01(j, tempV, ref bit[i, j]);
else
{
temp[i, j] = -1;
bit[i, j] = -1;
}
}
}
int i1, t, Top;
i1 = t = Top = 0;
findTop(temp, ref i1, ref t, ref Top);
this.i = i1;
this.t = t;
this.Top = Top;
this.Bit=transterInttoChar(bit[this.i,this.t]);
}
}
}
--------------------编程问答-------------------- 谢谢，大家的回答，我自己也写了一个。
第一次用才c#,可能有些漏洞，多多包涵
我是用普通的一维的字符矩阵存的这个2进为向量的
用一个2维的矩阵存可能的的k,然后在这个2纬数组里找出最大的，就是k,2维矩阵的两个下标就是b和c
大家差差阿，有什么错吗？
还有是不知道c#用不用类似于c++的delete的把new分配在heap上的动态空间删除了
怎么删除这些动态生成的矩阵呢〉？？
还有矩阵往函数里传是传参的阿。
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication6
{
class hashencoder
{
public int i;
public int t;
public char Bit;
public int Top;
public char[] Vector;
//initialize the Constructor of hashencoder
public hashencoder(char[] Vector)
{
this.Vector = Vector;
}
//start encoding
public void encoding()
{
calculatehash();
Console.WriteLine("After encoding :");
Console.WriteLine("Hash Value=(i({0}),t({1}),Bit({2});Top({3}))", this.i, this.t,this.Bit,this.Top);
}
// belows reverse the prefix of V from 1 to 0 , vice verse
static char[] reverse(char[] V, int prefix)
{
char[] temp = (char[])V.Clone();
for (int i = 0; i < prefix; i++)
{
if (temp[i] == '1')
temp[i] = '0';
else temp[i] = '1';
}
return temp;
}
//as follows,calculate the weight of the prefix of a vector
static int weight(char[] V, int prefix)
{
int count = 0;
for (int i = 0; i < prefix; i++)
{
if (V[i] == '1')
count++;
}
return count;
}
//as follows,calculate the weight of a vector
static int weight(char[] V)
{
int count = 0;
for (int i = 0; i < V.Length; i++)
{
if (V[i] == '1')
count++;
}
return count;
}
//as follows,display the vector
static void display(char[] V)
{
for (int i = 0; i < V.Length; ++i)
{
Console.Write(V[i]);
}
Console.WriteLine("");
}
// calulate the difference between 0'number and 1' of the l length of vector
static int difference01(int l, char[] V, ref int Bit)
{
Bit = 1;
int result;
result = 2 * weight(V, l) - l;
if (result < 0)
{
Bit = 0;
result = -result;
}
return result;
}
//caculate the biggest of the 2 dimmensional array.
static void findTop(int[,] b, ref int i, ref int t, ref int Top)
{
i = t = 1;
Top = b[1, 1];
for (int k = 1; k < b.GetLength(0); k++)
{
for (int j = 1; j < b.GetLength(1); ++j)
{
if (b[k, j] > Top)
{
Top = b[k, j];
i = k;
t = j;
}
}
}
}
// invert the vector from head to tail
static void invert(char[] V)
{
float n = (float)V.Length / 2 - V.Length / 2;
//if (((float)V.Length / 2 - V.Length/2) == 0)
char temp;
for (int i = 0, j = V.Length - 1; i < V.Length / 2; i++)
{
temp = V[i];
V[i] = V[i + j];
V[i + j] = temp;
j = j - 2;
}
}
//calculate the xor
static int xor1(int bit)
{
if (bit == 0)
bit = 1;
else
bit = 0;
return bit;
}
//transfer int to char
static char transterInttoChar(int i)
{
char c;
c = (i == 0 ? '0' : '1');
return c;
}
// calculate the hash value
private void calculatehash()
{
char[] V = this.Vector;
int[,] temp = new int[V.Length + 1, V.Length + 1];
int[,] bit = new int[V.Length + 1, V.Length + 1];
// int[][] temp = new int [V.Length][];
//int[][] bit = new int [V.Length][];
char[] tempV=new char[V.Length];
for (int i = 1; i <= V.Length; i++)
{
tempV = reverse(V, i);
//temp[i] = new int[V.Length];
//bit[i] = new int[V.Length];
int w = weight(tempV);
for (int j = 1; j <= V.Length; j++)
{
if (w == V.Length / 2)
temp[i, j] = difference01(j, tempV, ref bit[i, j]);
else
{
temp[i, j] = -1;
bit[i, j] = -1;
}
}
}
int i1, t, Top;
i1 = t = Top = 0;
findTop(temp, ref i1, ref t, ref Top);
this.i = i1;
this.t = t;
this.Top = Top;
this.Bit=transterInttoChar(bit[this.i,this.t]);
}
}
}
--------------------编程问答-------------------- 没有人回复吗？我想知道如何集成到matlab里用
就是matlab里调用这个类的对象。 --------------------编程问答-------------------- １：如何存这个Ｎ位的二进制向量Ｖ
２：存在很多中间的平衡向量如何存储，
３：这个实际的过程是个逆推的过程k知道了，推出c，和b
做法1：
1、建议使用一个超大的BigInt来保存，有助于你的运算，BigInt类型网络上有下载的，一般情况下，Int是4字节的，也就是32位，而BigInt可以设置到几个的1024位。
2、平衡向量也使用BigInt
3、不懂
做法1：
1、使用字符串来处理，也就是String，最好是StringBuild
2、使用字符串来处理，也就是String，最好是StringBuild
3、不懂
--------------------编程问答-------------------- cnming 你好
我最后是用字符串解决的问题，
但是，我编程的时候用console.readline();时候只能往屏幕上输入２５５个字符．
如何写着１０２４个呢，
用input buffer file应该可以吧，
但是有没有直接输的呢 --------------------编程问答-------------------- console.readkey(); --------------------编程问答-------------------- NB
补充：.NET技术 , C#
