Bézout's identity

3x+5y=11, x,yZ, look for (x,y) maximize (x+y)  under the condition: max(x+y)<= 100

#include<iostream>
using namespace std;
int main(){
 int a,b,c;
 cin>>a;
 cin>>b;
 cin>>c;
 int sum=0;
 for(int x=-1000;x<101;x++){

  int x1=x;
  int x2=(-1)*x;
  int y1=(c-a*x1)/b;
  int y2=(c-a*x2)/b;
  if( (y1<=100-x1) && (a*x1+b*y1==c))
  {
   cout<<x1<<" "<<y1<<endl;} 
   //cout<<x1+y1<<endl;
  if((x1+y1>sum)&&(x1+y1<101)/*&&(x1+y1==99)*/)
   {
    sum=x1+y1;
    
   }

  
  if( (y2<=100-x2) && (a*x2+b*y2==c))
  {
cout<<x2<<" "<<y2<<endl;
  //cout<<x2+y2<<endl;
  }
  if((x2+y2>sum)&&(x2+y2<101)/*&&(x2+y2==99)*/)
  {
   sum=x2+y2;
   
  }
 }

 cout<<sum;
 system("PAUSE");
}

貝祖定理(Bézout's identity)

ax+by=m, 求所有解中 x+y 最小的一組 (x,y>0)

輸入
第一行為筆數
之後每行有三個數字 for a b m
3
8 -7 1
13 -16 1
39 -7 1

輸出
1 1
5 4
2 11

#include<iostream>
using namespace std;
int main(){
 int i;
 cin>>i;
 while(i--){
  bool f=false;
  int a,b,c;
  cin>>a>>b>>c;
  for(int j=1;j<300000;j++){
   for(int k=1;k<300000;k++){
    if(a*j+b*k==c){
     cout <<j<<" "<<k<<endl;
     f=true;
           break;
    }
    
   }
   if(f==true){
    break;
    }
  }
 }
 system("PAUSE");
}

Staircase Walk: 走格子 (Stack)

0

1

2

3


4

5

6

7


8

9

10

11


n rows, m colums 

3 rows, 4 columns

/*
Staircase Walk: 走格子的版本, n rows, m columns
相當於 http://mathworld.wolfram.com/StaircaseWalk.html
n=n+1, m=m+1
*/

#include<iostream>
#include<stack>
using namespace std;
int main()
{   
 int n,m,count=0;
 stack<int> s;
 cin >> n >> m;
 s.push(0);
 while(!s.empty()){
  int c = s.top();s.pop();
  if (c==(n*m-1)){
   count++;
  }
  else{
   if ((c+1)%m!=0) s.push(c+1);   
   if ((c+m)<n*m) s.push(c+m);  
  }
 }
 cout << count;
 system("pause");
 return 0;
}

資訊之芽 動態規劃 Ex2. 塗色問題 4 種顏色的狀況

RGBY
Y:Yellow
Blue 後面不能是 Yellow
其餘條件同！

Array and init

#include <iostream> using namespace std; int globalArray[3]; int main(int argc, const char * argv[]) { int localArray[3]; int localArrayWithInit[3]={1}; for (int i=0;i<3;i++) cout << globalArray[i]; //000 cout << endl; for (int i=0;i<3;i++) cout << localArray[i]; //random cout << endl; for (int i=0;i<3;i++) cout << localArrayWithInit[i]; //100 return 0; }

資訊之芽 動態規劃

資訊之芽 動態規劃 Ex2. 塗色問題

#include <iostream>
using namespace std;
unsigned long long int F[1000001][3];
unsigned long long int f1(unsigned long long int m){
    F[1][0]=1;
    F[1][1]=1;
    F[1][2]=1;
    
    for (unsigned long long int n=2;n<=m;n++){
        F[n][0] =F[n-1][0]+F[n-1][1]+F[n-1][2];
        F[n][1] =F[n-1][1]+F[n-1][2];
        F[n][2] =F[n-1][0]+F[n-1][2];
        //cout << F[n][0]+ F[n][1]+ F[n][2] << ",";
        
    }
    return  F[m][0]+ F[m][1]+ F[m][2];
}
//https://oeis.org/A095263
unsigned long long int G[1000001];
unsigned long long int f2(unsigned long long int m){
    G[1]=3;
    G[2]=7;
    G[3]=16;
    
    for (unsigned long long int n=4;n<=m;n++){
        G[n]=3*G[n-1]-2*G[n-2]+G[n-3];
    }
    return G[m];
    
}

int main(int argc, const char * argv[])
{
    unsigned long long int m;
    cin >> m;
    cout << f1(m) << endl;
    cout << f2(m) << endl;
    return 0;
}