簡單記錄一下springboot引用kettle對接數據 第一步（這一步講述了下載kettle、創建資料庫連接、轉換等，如果這一步會的可以略過，直接看第二步） 先從kettle官網下載kettle，官網地址：https://sourceforge.net/projects/pentaho/ 進入官網 ...
在編寫程式解決某些問題時，可以靈活地使用進位制數，例如像二進位枚舉就是靈活使用二進位數。下麵再講述一些例題。
1、二進位的應用
【例1】至少一位數字相同
問題描述
給定N個正整數A1，A2，...，AN，求有多少整數對(i,j)，滿足以下條件：
1≤i<j≤N，Ai和Aj至少有一位數字是相同的（不一定要在相同的數位）。
輸入
輸入的第一行包含一個正整數N。
接下來N行，每行包含一個正整數Ai。
輸出
輸出一行一個整數，表示滿足條件的整數對的數目。
輸入樣例
4
32
51
123
282
輸出樣例
4
（1）編程思路。
以樣例為例說明。共有4組整數對滿足條件。（32，123）、（32，282）、（51，123）和（123，282）。
顯然，若採用二重迴圈兩兩組合來判斷每組數中是否至少有一位數字是相同的，在數據量較大的情況下，不是一個可取的方法。
實際上要判斷兩個整數是否至少有一位數字是相同的。我們是不在乎兩個數的每一個數位是什麼、哪幾個位上的數字相同，只用關心0~9這9個數字中是否有某個數字在兩個數中都出現過，若都出現過，則兩個數至少有一位數字是相同的。
由於十進位中只有0~9共10個數位，因此可以用一個10位的二進位數來表示一個十進位整數X的類型，這個二進位數的第k（0≤k≤9）位為1表示整數X中含有數字k，若數字k在整數X中沒出現，則對應二進位數的第k位為0。
用數組a來保存各類型整數的個數，顯然任何一個正整數的類型一定在 [0,1023]之間。即數組a最多有1024個元素。初始時，數組a的元素值全部置為0。
還是以樣例中的4個數為例。
整數32中含有2、3這兩個數字，對應二進位數為0000001100，數的類型號為12，a[12]加1，a[12]=1。
整數51中含有1、5這兩個數字，對應二進位數為0000100010，數的類型號為34，a[34]加1，a[34]=1。
整數123中含有1、2、3這3個數字，對應二進位數為0000001110，數的類型號為14，a[14]加1，a[14]=1。
整數282中含有2、8這兩個數字，對應二進位數為0100000100，數的類型號為260，a[260]加1，a[260]=1。
這樣處理後，再求N個正整數中滿足要求的整數對的數量ans（初值為0）就很方便了。分兩種情況處理。
1）兩個整數的類型相同，則同類型中任意取兩個數就滿足要求。用迴圈對a[0]~a[1023]中各a[i]值進行遍歷。若 a[i]!=0，則 ans=ans+a[i]*(a[i]-1)/2。
2）兩個整數的類型不同。設一個類型為i，一個類型為j （設i<j），若 i & j的值不為0，則i和j對應的二進位數一定在某個位上都是1，也就是存在相同的數字（某個位都為1）。這樣，a[i]和a[j]中各取1個數就滿足要求。 ans=ans+a[i]*a[j]。
（2）源程式。
#include <stdio.h> int main() { int n; scanf("%d",&n); int i,j; long long a[1024]={0}; int min=1024,max=0; for (i=1;i<=n;i++) { long long x; scanf("%lld",&x); int h[10]; // 記錄0~9每個數字在x中是否出現 for (j=0;j<10;j++) h[j]=0; while(x) { h[x%10]=1; // 數字x%10出現了，h[x%10]記為1 x/=10; } int num=0; for (j=0;j<10;j++) { num=num*2+h[j]; // 將h[0]~h[9]中保存數據作為二進位數轉換為十進位數num } a[num]++; // num這種數增加1個 if (num>max) max=num; if (num<min) min=num; } long long ans=0; for (i=min;i<=max;i++) // 同一種數內兩兩組合 ans+=a[i]*(a[i]-1)/2; for (i=min;i<max;i++) // 不同種類的數兩兩組合 { for (j=i+1;j<=max;j++) if (i & j) ans+=a[i]*a[j]; } printf("%lld\n",ans); return 0; }
將上面的源程式提交給洛谷題庫 P7617 [COCI2011-2012#2] KOMPIĆI （https://www.luogu.com.cn/problem/P7617），可以Accepted。
【例2】異或和
問題描述
給定一個長度為N的序列A1，A2，...，AN，求序列元素兩兩異或的總和。
例如，某序列中有3個數，A1=7，A2=3，A3=5。
則有 A1 ⊕ A2 = 4，A1 ⊕ A3 = 2，A2 ⊕ A3 = 6，
4 + 2 + 6 = 12，因此序列元素兩兩異或的總和為12。
輸入
輸入的第一行包含一個正整數N（1≤N≤106）。
接下來N行每行包含一個正整數Ai（1≤Ai≤106）。
輸出
輸出一行一個整數，表示兩兩異或後的總和。
輸入樣例
3
7
3
5
輸出樣例
12
（1）編程思路。
若通過二重迴圈對序列中的數據進行兩兩組合求異或和，在數據量大的情況下肯定是超時的。
首先，我們考慮一個數轉成二進位後每個位的操作，每個位上的數據只能是0或1，其異或運算規則是： 0和1 異或得1 ， 1和1 或者 0和 0 異或得0 。怎麼求多個0 和1 的兩兩異或和呢？
舉個例子： 0，1，0 三個數兩兩異或和應該是：0 異或 1 加上 0 異或0 再加上 1 異或 0，和值sum=1+0+1=2 。從中可以發現，每個 0 和一個 1 進行異或，和sum 就要加 1 ，也就是說每一個 0 都會使 sum 加上 1 的個數（因為 0 要和 1 的個數個 1 異或）。設在n個0、1序列中有x 個1 ，則有 n-x個0，這樣兩兩異或的和值sum 就等於 0 的個數乘 1 的個數，也就是 sum=(n−x)*x 。
現在要對N個正整數序列求兩兩異或和。具體做法是：
將原序列中的每個元素都轉換為二進位，並用一個數組 a 記錄序列中全部元素各二進位數中每一位1 的個數。最後用一個迴圈，將二進位每一位的兩兩異或和都算出來，累加到和值sum中。
n 個數中第i 位上每一對 0 和 1 都能造成 2i 的貢獻。在n個數中，已求出各二進位數第i位上有a[i]個 1，有 n-a[i]個 0，而每個 0都和a[i]個 1 都能造成2i的貢獻，所以
sum=sum+a[i]*(n−a[i])*2i 。
以樣例為例說明。7 對應二進位數為 111，因此，a[0]=a[0]+1，a[1]=a[1]+1，a[2]=a[2]+1，由此，a[0]=1，a[1]=1，a[2]=1。
3 對應二進位數為 11，因此，a[0]=a[0]+1，a[1]=a[1]+1，由此，a[0]=2，a[1]=2，a[2]=1。
5 對應二進位數為 101，因此，a[0]=a[0]+1，a[2]=a[2]+1，由此，a[0]=3，a[1]=2，a[2]=2。
為此，在異或和的和值sum中， 第0位貢獻 3*0*1=0，第1位貢獻 2*(3-2)*2=4，第2位貢獻 2*(3-2)*4=8。因此，和值sum=0+4+8=12。
（2）源程式。
#include <stdio.h> int main() { int n; scanf("%d",&n); int i,a[25]={0},len=0; for (i=1;i<=n;i++) { int x; scanf("%d",&x); int k=0; while(x) // 將x轉為二進位 { a[k]=a[k]+x%2; // 如果第k位是1，則a[k]加1 x/=2; k++; } if (len<k) len=k; // 各數對應二進位數的最長位數 } long long ans=0; for (i=0;i<len;i++) ans+=1ll*a[i]*(n-a[i])*(1<<i); printf("%lld\n",ans); return 0; }
2、三進位的應用
【例3】天平稱重
問題描述
給你一臺天平，一件貨物重m公斤。然後給你一些重1，3，9，27，…，3^k的砝碼。當然，不同權重的砝碼數量只有一個。
現在把貨物放在天平的左邊。然後你應該在天平的兩邊放一些砝碼，使天平平衡。
輸入
整數m表示貨物的重量（0≤ m≤ 100 000 000)
輸出
您應該輸出兩行。
在第一行中，第一個整數N1是放在天平左邊的砝碼的數量，然後N1個整數（按升序），表示放在左邊的各砝碼的重量，每個數用一個空格隔開。
在第二行中，請使用與第一行相同的方式輸出N2，即右側放置的砝碼數。然後，按照升序排列的N2個整數表示放在右邊的各砝碼的重量。
輸入樣例
42
30
輸出樣例
3 3 9 27
1 81
0
2 3 27
（1）編程思路。
可以看出砝碼重量1、3、9、27、…正好是一個三進位數各位上的權值，因此應考慮三進位數的應用。
稱重時砝碼可以放在左盤（物體盤），也可以放在右盤（砝碼盤）。若砝碼只放在右盤，則 物體質量=砝碼盤砝碼質量；若右盤和左盤中都放置了砝碼，則 物體質量=右盤砝碼質量-左盤砝碼質量。這樣，由於可以把砝碼加在天平的左盤中，因此，放在左盤中的砝碼不是要加在稱出的質量上面，而是要從中減去的數。例如，5=9-3-1、6=9-3、7=9+1-3等等。
為了達到這個目的，設所用的三進位數位不是通常的0、1、2，而是-1、0、1。即2可以寫成3-1，將其轉化成-1這個數字。為了描述簡便，把-1寫成i，以後只要在三進位中碰到2這個數字，就把它改寫成1i（即3-1=2）。例如，三進位中的22102這個數，可以用下麵的方法改寫成10i11i。
22102 = 20000 + 2000 + 100 + 2 = 1i0000 + 1i000 +100 + 1i
= 1i0000 + 1i000 +11i = 1i0000 + 1i11i = 10i11i
來看幾個實際克數的稱重情況。
例如，為了稱出14克，先將14化成普通三進位112，再進行改寫，112=100+10+1i=100+2i=100+20+i = 100 +1i0 +i =100 +1ii = 2ii =1iii。這就是說，把27這塊砝碼放進右盤，而把9、3、1三塊砝碼放進左盤中，就可以稱出14克出來（27-9-3-1=14）。
再看怎樣稱出26克來，26化成普通三進位222，進行改寫，222=1i00+1i0+1i=1i00+10i=100i。這就是說，把27這塊砝碼放進右盤，而把1這塊砝碼放進左盤中，就可以稱出26克出來（27-1=26）。
因此，本題的處理辦法是：
先將輸入的十進位數n轉換為3進位數，轉換後得到的各位三進位數字保存在數組a中。然後對數組a中的值從低位向高位進行校正。校正方法為：
若 a[i]的值為2，則變為 -1， 同時 a[i+1]加1（相當於向前1位進位）；
若 a[i]的值為3，則變為 0， 同時向前1位進位，即 a[i+1] 加1；
若 a[i]的值 為0 或 1 時保持不變。
之後將a[i]值為1所對應的重為3i的砝碼放在右盤中，a[i]值為-1 所對應的重為3i的砝碼放在左盤中，就是問題的答案。
（2）源程式。
#include <stdio.h> int main() { int table[21]; // table[i]保存3的i次方的值 table[0]=1; int i; for (i = 1; i < 20; i++) // 預先求得3的1次方~3的19次方值保存到數組table中 table[i]=table[i-1]*3; int n; while (scanf("%d", &n)!=EOF) { int len = 0; int a[21]; while (n!=0) // 將n轉換為3進位數，並將各位數字保存到數組a中，a[0]保存最低位數字 { a[len++] = n % 3; n = n / 3; } a[len]=0; // 最高位的前面先補個0 int lcnt=0,rcnt=0; // 分別保存放在天平左端和天平右端的砝碼個數 for (i=0;i<len;i++) // 從低位到高位對3進位數進行校正 { if (a[i]==1) rcnt++; if (a[i]==2) { a[i]=-1; a[i+1]++; lcnt++; } if (a[i]==3) { a[i]=0; a[i+1]++; } } if (a[len]!=0) { rcnt++; len++; } printf("%d",lcnt); for (i=0;i<len;i++) if (a[i]==-1) printf(" %d",table[i]); printf("\n"); printf("%d",rcnt); for (i=0;i<len;i++) if (a[i]==1) printf(" %d",table[i]); printf("\n"); } return 0; }
將上面的源程式提交給 HDU 3029 Scales （http://acm.hdu.edu.cn/showproblem.php?pid=3029），可以Accepted。
