#
1。完成曹雪的語法分析器
2。完成葉慶生的項目
3。有道難題的資格賽 （周六晚）
4。復習和總結動態(tài)規(guī)劃專題（包括那個自學的內容）
The MS-RT professional masters degree program trains future leaders of robotics and intelligent automation enterprises and agencies in the principles and practices of robotics and automation science and engineering, software engineering, and management. The program is appropriate for students with backgrounds in an engineering or science discipline and practical abilities in computer systems and software engineering. Classroom training is reinforced by an extensive supervised practicum designed to expose the students to research laboratory and industrial environments. They will thus acquire - and be expected to demonstrate - individual and group competence in the skills and practices that will be needed to support the entrepreneurial teams they will lead upon their return to their home countries.
The two-year program is composed of two one-year phases. First year studies are at an international partner institution's campus via distance education materials produced by the Robotics Institute and delivered by the partner's faculty. Successful students transition to Carnegie Mellon's main campus to complete a second year of classes and an extensive practicum. Graduates are eligible to pursue additional practical training in the US before returning to their home countries.
Preferably the additional training will be an internship with a company in the US that, afterwards, will employ the student at a division in his or her home country. The program's intention is for graduates to return home to entrepreneurial activities that will contribute to sustainable development there.
Historical Note: In 2005 some graduates of this program received Master of Science in Information Technology - Robotics Technology (MSIT-RT) degrees and others received MSIT degrees. In 2006 and 2007 all graduates received MSIT-RT degrees. Subsequently the program name was changed to Master of Science - Robotics Technology (MS-RT) to better reflect its actual content. For additional simplicity, all graduates are listed here as having received MS-RT degrees.
Additional information
摘要: 這題出得不錯，在傳統(tǒng)的bfs上加了點改進，好題~
#include<iostream>#include<cmath>using namespace std;int const maxn=110;int mm[maxn][maxn];int v[maxn][maxn][4];//0上，1右，2下，3左struct&...
閱讀全文
周五剛好在俞研的網(wǎng)絡安全課上學了RSA，回來想實現(xiàn)以下，由于以前數(shù)論方面的積累還算比較深厚，很快就過了這一題，呵呵:-)
總結一下吧，這題可以說是數(shù)論部分的一個大綜合題，因為它將算法導論上數(shù)論這部分的知識點全部包含了進來，包括gcd,擴展gcd,模線性方程，a^b mod c(還是比較難的那種，相關題目可以看一下FOZ上面的2道題),miller-rabin素數(shù)測試，pollard_rho質因數(shù)分解等等，把這題搞定了說明你對算法導論的數(shù)論部分已經(jīng)可以做到熟練掌握了，相當于<算法導論>數(shù)論部分的期末測試，呵呵^_^。
下面簡要的說一下這題的做法，首先簡要介紹一下RSA算法加密解密的過程：
我們首先生成兩個大的素數(shù)P,Q,乘起來得
N=P*Q.然后算出N的歐拉函數(shù)
Phi(N)=(P-1)*(Q-1).(什么是歐拉函數(shù)？這個世界上有一種東西叫做百度...）,然后我們取一個范圍在
[1,phi(N)]中且與phi(N)互質的正整數(shù)E.它就是所謂的公鑰。得到公鑰之后，我們再算出E關于
phi(N)的逆元D,即E*D mod phi(N)=1.這個D就是私鑰。在得到這些數(shù)據(jù)以后，P,Q被丟棄，E,N做為公鑰被公開，D做為私鑰被解密人私人保存。
好了，下面看一下如何用公鑰和私鑰對數(shù)據(jù)進行加密解密。
假設有一個明文M,那么它所對應的密文就是
C=M^E mod N.如果我們現(xiàn)在得到一個密文C,那么它所對應的明文就是
M=C^D mod N也就是說，任何人都可以用公鑰對數(shù)據(jù)進行加密，但是只有擁有私鑰的人才可以對數(shù)據(jù)進行解密。
那么RSA算法為什么不易被破解呢？從解密的過程來看如果你能夠知道D那么你就能解密數(shù)據(jù)。而E,D是逆元關系，要求出D,需要知道phi(N)，由于N非常之大，普通的做法是從1開始枚舉到N-1，計算和N互質的元素個數(shù)。可是N可以是幾百位到上千位的數(shù)字，普通的計算機只能在1s內算到10^8量級，顯然是不可能破解的。唯一有可能的方法基于大素數(shù)分解，如果你能將N分解成P*Q的乘積。那么就可以直接利用公式phi(N)=(P-1)*(Q-1)繞開暴力求解歐拉函數(shù)的過程，從而實現(xiàn)RSA的破解。
這道題就是模擬這個破解過程，下面來說說具體的做法：
1.首先用miller-rabin,pollard_rho做大整數(shù)的質因數(shù)分解，得到兩個素數(shù)P,Q，pollard_rho的復雜度在N^0.25次方，那么一個64位的整數(shù) 要計算的次數(shù)為 2^64^0.25=2^16 =65536次，可以瞬間出解。
2.求出phi(N)=(P-1)*(Q-1)
3.然后用ext_gcd求出E關于phi(N)的逆元。
4.用得到的私鑰對數(shù)據(jù)C進行解密即可。
PS:對這題而言，僅僅完成上述步驟還是不夠的。因為N達到2^62次方，即使是使用無符號long long ,也很容易因為出乘法操作而溢出。這也是網(wǎng)上說要避免使用擴展歐幾里德的原因。其實實現(xiàn)的時候，我們可以自己寫一個特殊的乘法（內部用加法實現(xiàn)），由于使用的無符號的long long ，第64位剛好可以用來保存兩個數(shù)加過之后的進位位，再模除又可以保證其在2^62范圍內，即可避免溢出。
摘要: 做完心情不太好，1000分的水題居然因為自己開小了數(shù)組而掛掉。算了，不解釋。250
#include<iostream>#include<algorithm>#include<cstdio>#include<string>#include<vector>using namespace std;struct ...
閱讀全文
剛好課上學了平面最近點對的算法，回來實現(xiàn)以下，恩 ，分治的思想很重要。呵呵，又學會了一個算法。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define eps 1e-8
const int maxn=200001;
const double INF=999999999;
typedef struct point
{
double x,y;
//int flag;
point(){};
}point;
point p[maxn];
int n;
int cmp(double x,double y)
{
if(x==y)return 0;
if(x>y)return 1;
return -1;
}
bool cmp1(point a,point b)
{
if(a.x!=b.x)
return a.x<b.x;
else
return a.y<b.y;
}
bool cmp2(int i,int j)
{
return cmp(p[i].y,p[j].y)<0;
}
double dist(point &a,point &b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int y[maxn],len;
double cp(point p[],int l,int r)//求從l到r這些點的最近點對
{
int i,j;
int mid=(l+r)>>1;
double ret=INF;
if(l>=r)
return ret;
for(i=mid;i>=l&&!cmp(p[i].x,p[mid].x);i--);
double t1=cp(p,l,i);
for(i=mid;i<=r&&!cmp(p[i].x,p[mid].x);i++);
double t2=cp(p,i,r);
if(t1<t2)
ret=t1;
else ret=t2;
len=0;
for(i=l;i<=r;i++)
{
if(fabs(p[i].x-p[mid].x)<ret)
y[++len]=i;
}
sort(y+1,y+len+1,cmp2);
for(i=1;i<=len;i++)
{
int cnt=1;
for(j=i+1;j<=len&&cnt<=7;j++)
{
ret=min(ret,dist(p[y[i]],p[y[j]]));
cnt++;
}
}
return ret;
}
bool check(int n)
{
int i;
for(i=2;i<=n;i++)
{
if(p[i].x==p[i-1].x&&p[i].y==p[i-1].y)
return true;
}
return false;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
break;
int i;
for(i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
sort(p+1,p+n+1,cmp1);
if(check(n))
{
printf("0.00\n");
continue;
}
double ans=cp(p,1,n)/2;
printf("%.2lf\n",ans);
}
return 0;
}
越來越發(fā)現(xiàn) 其實學生的水平 很大程度上還是依賴學校的綜合實力 畢竟我們學到的東西一大部分都是從老師那里來的 看來還是要多和外校的老師和同學交流才行啊。
取整函數(shù)的一些性質：
• x-1 < ëxû £ x £ éxù < x+1；
• ë n/2 û + é n/2 ù = n;
• 對于n ³ 0，a,b>0，有：
• é é n/a ù /b ù = é n/ab ù ;
• ë ë n/a û /b û = ë n/ab û ;
• é a/b ù £ (a+(b-1))/b; (函數(shù)值的緊上界)
• ë a/b û ³ (a-(b-1))/b; (函數(shù)值的緊下界)
• f(x)= ë x û , g(x)= é x ù 為單調遞增函數(shù)
/////////////////////快速排序,時間復雜度為O(nlog2n)///////////////////////
template<class T>
int Partion(T a[],int i,int j)//劃分函數(shù)
{
T temp;
temp=a[i];
while(i<j)
{
while(i<j && temp<=a[j])
j--;
if(i<j)
{
a[i]=a[j];
i++;
}
while(i<j && a[i]<=temp)
i++;
if(i<j)
{
a[j]=a[i];
j--;
}
}
a[i]=temp;
return i;
}
template <class T>
void qsort(T a[],int l,int h)
{
int m;
if(l<h)
{
m=Partion(a,l,h);
qsort(a,l,m-1);
qsort(a,m+1,h);
}
}
template<class T>
void SortWizard<T>::QuickSort()
{
qsort(a,0,n-1);
}
/**/////////////////////QuickSort_O(nlog2n)////////////////////////
/**////////////////////////歸并排序,時間復雜度O(nlog2n)/////////////////////////////
template <class T>
void Merge(T sr[],T tr[],int l,int m,int n)
{
int i,j,k;
i=l;
j=m+1;
k=l-1;
while(i<=m && j<=n)
{
if(sr[i]<sr[j])
tr[++k]=sr[i++];
else
tr[++k]=sr[j++];
}
while(i<=m)
tr[++k]=sr[i++];
while(j<=n)
tr[++k]=sr[j++];
for(i=l;i<=n;i++)
sr[i]=tr[i];
}
template <class T>
void Msort(T a[],T st[],int s,int t)
{
int m;
if(s<t)
{
m=(s+t)>>1;
Msort(a,st,s,m);
Msort(a,st,m+1,t);
Merge(a,st,s,m,t);
}
}
template <class T>
void SortWizard<T>::MergeSort()
{
T *st=new T[n];
Msort(a,st,0,n-1);
delete [ ]st;
}
/**//**//**///////////////////////MergeSort_O(nlog2n)///////////////////////////////