?? 連續串之和.txt
字號:
#include <iostream>
#include <stdio.h>
using namespace std;
//連續串之和
/*
輸入
8
4
輸出
0
1
2
1
0
-1
0
1
問題轉述:
給出一個具有性質A的串集P和一個具有性質B的串集Q,試判斷P Q是否是空集。若不是,試給出其中的一個元素。
分析:
這一題目顯然無法把所有可能的串都搜索出來然后一一判斷,所以應當根據具體的性質進行剪枝,排除不可能的串;或更直接的,構造出答案。
考慮一個長度為n的連續串a,我們把它的元素從左端開始標號為1、2、…、n,并用ai表示第i(1 i n)個元素。由于連續串的性質是用相鄰兩整數之差定義的,故直接考慮元素的性質比較麻煩,我們再定義一個串b,為串a的性質串,其中有bi=ai+1-ai(1 i n-1)。這樣,我們可知這個串中所有元素之和 。這里bi只有-1和1兩種選擇。因為用負數計算還是比較麻煩,所以我們設ci=bi+1,這樣就有 。這里ci的取值為0或2,這時問題就轉化成了一個不完全的不等進位制問題。為了完善這個表達,我們再設dn-i=ci/2??芍?,也就是 。由于di的取值只有0和1,故該問題已經完全的轉化成了一個不等進位制問題。
我們可以知道0到 之間的整數均可以用 表示出來 ,而 的最大值為 ,最小值為0,并且又是整數。故我們得到了一個判定有解的方法。對于一個有解的問題,我們可以用如下的算法求出d的值:
1. k←n-1;
2. 如果T k,那么T←T-k,dk←1,否則dk←0;
3. k←k-1;
4. 如果k=0則退出,否則轉2。█
由于算法開始時 ,這樣如果T k,則 ;否則 。所以無論算法開始時T的值如何(當然,需要符合條件),執行一次后均有 。故在最后一次執行后 。又由于T在算法執行過程中非負,所以T=0。故算法必然正確。
最后,根據求出的di值代回求出ai就可以了。
總結:
為了在問題的特殊性質中挖掘可用的信息,通常都需要一些數學方面的技巧。在這一題的解題過程中,我們就可以看到數學技巧是如何應用的。
*/
#define NMAX 20
int x[NMAX];
int yuan[NMAX];
int temp[NMAX];
void cal(int num,int s1)
{
int s2,sum,i;
s2=num*(num-1)/2;
sum=(s1+s2)/2;
cout<<sum<<endl;
for(i=num-1;i>0;i--)
{
if(sum>=i)
{
sum-=i;
x[i]=1;
}
else x[i]=0;
temp[num-i]=2*x[i]-1;
}
yuan[0]=0;
for(i=1;i<num;i++)
yuan[i]=yuan[i-1]+temp[i];
}
void print(int num)
{
int i;
for(i=0;i<num;i++)
cout<<yuan[i]<<" ";
cout<<endl;
}
int main()
{
int num,sum;
scanf("%d%d",&num,&sum);
if(num%2==1) cout<<"NO SUCH STRING"<<endl;
else
{
cal(num,sum);
print(num);
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -