演算法4代碼

⑴ 1，2，3，4依次進棧，出棧隨時，寫一演算法求出所有可能出棧序列

代碼如下：

#define N 4

int m=0,a=0,b=N;/*m表示種數，a表示棧中元素個數，b表示外面還有需要進棧的個數*/

main()

{

inS(a,b);/*首先入棧*/

printf("%d",m);

getch();

}

int inS(int a,int b)/*入棧*/

{

a++;b--;/*入棧棧中元素+1，棧外元素-1 */

if(b>0)/*若棧外有元素，可以入棧*/

inS(a,b);

if(a>0)/*若棧中有元素，可以出棧*/

outS(a,b);

}

int outS(int a,int b)/*出棧*/

{

a--;/*出棧棧中元素-1*/

if(a==0&&b==0)/*若棧中元素和棧外元素都為0個*/

{

m++;/*則此種情況的序列滿足條件，種數+1*/

return;

}

if(b>0)

inS(a,b);

if(a>0)

outS(a,b);

}

(1)演算法4代碼擴展閱讀

棧的相關知識點：

順序棧內容包含數據和棧頂指針(int)，因此採用結構體。

注意：

1、初始時，top指向-1；

2、入棧讓敏橡時，先判斷順序棧是否已滿（判斷條件：top=maxsize-1）;如果沒滿，則top++，並將元素值賦給s.top;

3、出棧時，先判斷順序棧是否已拿圓空（判斷條件：top=-1）;如果沒空，則先返回棧頂元素，再top- -。

共享棧

兩個順序棧共坦旁享一個一維數組空間，而棧底位置相對不變，兩個棧底分別設為一維數組的兩端。

note:

(1)棧空：top1==-1&&top2==maxsize;

(2)棧滿：top2-top1= 1(此時兩個棧頂指針相鄰)；

(3)入棧：S.data[++top1]=x或S.data[–top2]=x;

(4)出棧：x=S.data[top1–]或x=S.data[top2++];

(5)共享棧可以更好的利用存儲空間，整個存儲空間被占滿時發生上溢。

⑵ 經典筆試面試知識整理，數據結構與演算法(代碼演示)

題目描述：

在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

輸入描述: array： 待查找的二維數組 target：查找的數字

輸出描述:

查找到返回true，查找不到返回false

題目描述：

請實現一個函數，將漏祥一個字元串中的空格替換成「%20」。例如，當字元串為We Are Happy.則經過替換之後的字元串為We%20Are%20Happy。

題目描述： 輸入一個鏈表，從尾到頭列印鏈表每個節點的值。

輸入描述： 輸入為鏈表的表頭

輸出描述： 輸出為需要列印的「新鏈表」的表頭

題目描述：

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。

例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹並返回。

題目描述：

把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一喊搜鉛個旋轉，輸出旋轉數組的最小元素。

例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。 NOTE：給出的所有元素都大於0，若數組大小為0，請返回0。

1、題目描述：

大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項。n<=39

2、題目描述：

一隻青蛙一次可以跳上1級台階，也可以跳上2級。求該青蛙跳上一個n級的台階總共有多少種跳法。

3、題目描述：

一隻青蛙一次可以跳上1級台階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的台階總共有多少種跳法。

4、題目描述：

我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？

1、題目描述：

輸入一個整數，輸出該數二進製表示中1的個數。其中負數用補碼表示。

2、題目描述：

給定一個double類型的浮點數base和int類型的整數exponent。求base的exponent次方。

題目描述：

輸入一個整數數組，實現一個函數來調整鄭好該數組中數字的順序，使得所有的奇數位於數組的前半部分，所有的偶數位於位於數組的後半部分，並保證奇數和奇數，偶數和偶數之間的相對位置不變。

題目描述：

用兩個棧來實現一個隊列，完成隊列的Push和Pop操作， 隊列中的元素為int類型。

題目描述：

輸入一個鏈表，輸出該鏈表中倒數第k個結點。

⑶ 演算法(第4版)給的兩個jar包stdlib.jar和algs4.jar要怎麼用

我只是導入了stdlib.jar，是導入到external（外部的） jars，然後編譯時還是會有問題，不過按照錯誤給的提示（忘記提示是什麼了），然後enter一下就可以了，之後編譯成功，並且在我所創建的項目中多了一個「引用 的庫」。

⑷ 求：用java語言編寫的銀行家演算法的源代碼

import java.util.*;

class ThreadTest {
static int type = 4, num = 10; //定義資源數目和線程數目
static int[] resource = new int[type]; //系統資源總數
//static int[] Resource = new int[type]; //副本
static Random rand = new Random();
static Bank[] bank = new Bank[num]; //線程組
Bank temp = new Bank();

public void init() {
//初始化組中每個線程，隨機填充系統資源總數
for(int i = 0; i < type; i++)
resource[i] = rand.nextInt(10) + 80;
System.out.print("Resource:");
for(int i = 0; i < type; i++)
System.out.print(" " + resource[i]);
System.out.println("");
for(int i = 0; i < bank.length; i++)
bank[i] = new Bank("#" + i);
}
public ThreadTest4() {
init();
}

class Bank extends Thread {
//銀行家演算法避免死鎖
public int[]
max = new int[type], //總共需求量
need = new int[type], //尚需資源量
allocation = new int[type]; //已分配量
private int[]
request = new int[type], //申請資源量
Resource = new int[type]; //資源副本
private boolean isFinish = false; //線程是否完成
int[][] table = new int[bank.length][type*4]; //二維資源分配表

private void init() {
// 隨機填充總共、尚需、已分配量
synchronized(resource) {
for(int i = 0; i < type; i++) {
max[i] = rand.nextInt(5) + 10;
need[i] = rand.nextInt(10);
allocation[i] = max[i] - need[i];
resource[i] -= allocation[i]; //從系統資源中減去已分配的
}
printer();
for(int i = 0; i < type; i++) {
if(resource[i] < 0) {
//若出現已分配量超出系統資源總數的錯誤則退出
System.out.println("The summation of Threads' allocations is out of range!");
System.exit(1);
}
}
}
}

public Bank(String s) {
setName(s);
init();
start();
}
public Bank() {
//none
}

public void run() {
try {
sleep(rand.nextInt(2000));
}
catch(InterruptedException e) {
throw new RuntimeException(e);
}
while(true) {
//程序沒有完成時一直不斷申請資源
if(askFor() == false) {
try {
sleep(1000);
}
catch(InterruptedException e) {
throw new RuntimeException(e);
}
}
else
tryRequest();
if(noNeed() == true)
break;
}
//休眠一段時間模擬程序運行
try {
sleep(1000);
}
catch(InterruptedException e) {
throw new RuntimeException(e);
}
System.out.println(getName() + " finish!");
synchronized(resource) {
//運行結束釋放佔有資源
for(int i = 0; i < type; i++) {
resource[i] += allocation[i];
need[i] = allocation[i] = max[i] = 0;
}
}
}

private void printer() {
//列印當前資源信息
System.out.print(getName() + " Max:");
for(int i = 0; i < type; i++)
System.out.print(" " + max[i]);
System.out.print(" Allocation:");
for(int i = 0; i < type; i++)
System.out.print(" " + allocation[i]);
System.out.print(" Need:");
for(int i = 0; i < type; i++)
System.out.print(" " + need[i]);
System.out.print(" Available:");
for(int i = 0; i < type; i++)
System.out.print(" " + resource[i]);
System.out.println("");
}
private boolean askFor() {
//隨機產生申請資源量並檢測是否超標
boolean canAsk = false;
for(int i = 0; i < type; i++) {
request[i] = rand.nextInt(20);
//防止申請量超過所需量
if(request[i] > need[i])
request[i] = need[i];
}
for(int i = 0; i < type; i++) //防止隨機申請資源全為0
if(request[i] > 0)
canAsk = true;
synchronized(resource) {
//鎖住可供資源檢查是否超標
for(int i = 0; i < type; i++) {
if(request[i] > resource[i])
//如果申請資源超過可供資源則等待一段時間後重新申請
return false;
}
}
return canAsk;
}
private void tryRequest() {
//創建副本嘗試分配請求
synchronized(resource) {
for(int i = 0; i < type; i++)
//依然要防止請求量超出范圍
if(request[i] > resource[i])
return;
for(int i = 0; i < type; i++) {
//復制資源量並減去需求量到一個副本上
Resource[i] = resource[i];
Resource[i] -= request[i];
}
System.out.print(getName() + " ask for:");
for(int i = 0; i < type; i++)
System.out.print(" " + request[i]);
System.out.println("");
if(checkSafe() == true) {
//如果檢查安全則將副本值賦給資源量並修改佔有量和需求量
for(int i = 0; i < type; i++) {
resource[i] = Resource[i];
allocation[i] += request[i];
need[i] -= request[i];
}
System.out.println(getName() + " request succeed!");
}
else
System.out.println(getName() + " request fail!");
}
}
private boolean checkSafe() {
//銀行家演算法檢查安全性
synchronized(bank) {
//將線程資源信息放入二維資源分配表檢查安全性，0~type可用資源／type~type*2所需資源／type*2~type*3佔有資源／type*3~-1可用+佔用資源
for(int i = 0; i < bank.length; i++) {
for(int j = type; j < type*2; j++) {
table[i][j] = bank[i].need[j%type];
}
for(int j = type*2; j < type*3; j++) {
table[i][j] = bank[i].allocation[j%type];
}
}
//冒泡排序按需求資源從小到大排
for(int i = 0; i < bank.length; i++) {
for(int j = i; j < bank.length-1; j++) {
sort(j, 4);
}
}
//進行此時刻的安全性檢查
for(int i = 0; i < type; i++) {
table[0][i] = Resource[i];
table[0][i+type*3] = table[0][i] + table[0][i+type*2];
if(table[0][i+type*3] < table[1][i+type])
return false;
}
for(int j = 1; j < bank.length-1; j++) {
for(int k = 0; k < type; k++) {
table[j][k] = table[j-1][k+type*3];
table[j][k+type*3] = table[j][k] + table[j][k+type*2];
if(table[j][k+type*3] < table[j+1][k+type])
return false;
}
}
}
return true;
}
private void sort(int j, int k) {
//遞歸冒泡排序
int tempNum;
if(table[j][k] > table[j+1][k]) {
for(int i = type; i < type*2; i++) {
tempNum = table[j][i];
table[j][i] = table[j+1][i];
table[j+1][i] = tempNum;
}
/*temp = bank[j];
bank[j] = bank[j+1];
bank[j+1] = temp;*/
}
else if(table[j][k] == table[j+1][k] && k < type*2) //此資源量相同時遞歸下一個資源量排序並且防止超出范圍
sort(j, k+1);
}
private boolean noNeed() {
//是否還需要資源
boolean finish = true;
for(int i = 0; i < type; i++) {
if(need[i] != 0) {
finish = false;
break;
}
}
return finish;
}
}

public static void main(String[] args) {
ThreadTest t = new ThreadTest();
//後台線程，設定程序運行多長時間後自動結束
new Timeout(30000, "---Stop!!!---");
}
}

⑸ 用C++編寫一個洗牌發牌的函數，玩家可能有兩個、三個和四個

幾乎所有的程序員都寫過類似於「洗牌」的演算法，也就是將一個數組隨機打亂後輸出，雖然很簡單，但是深入研究起來，這個小小的演算法也是大有講究。我在面試程序員的時候，就會經常讓他們當場寫一個洗牌的函數，從中可以觀察到他們對於這個問題的理解和寫程序的基本功。

在深入討論之前，必須先定義出一個基本概念：究竟洗牌演算法的本質是什麼？也就是說，什麼樣的洗牌結果是「正確」的？

雲風曾經有一篇博文，專門討論了這個問題，他也給出了一個比較確切的定義，在經過洗牌函數後，如果能夠保證每一個數據出現在所有位置的概率是相等的，那麼這種演算法是符合要求的。在這個前提下，盡量降低時間復雜度和空間復雜度就能得到好的演算法。

第一個洗牌演算法：

隨機抽出一張牌，檢查這張牌是否被抽取過，如果已經被抽取過，則重新抽取，直到找到沒被抽出過的牌，然後把這張牌放入洗好的隊列中，重復該過程，直到所有的牌被抽出。

大概是比較符合大腦對於洗牌的直觀思維，這個演算法經常出現在我遇到的面試結果中，雖然它符合我們對於洗牌演算法的基本要求，但這個演算法並不好，首先它的復雜度為O(N2)，而且需要額外的內存空間保存已經被抽出的牌的索引。所以當數據量比較大時，會極大降低效率。

第二個演算法：

設牌的張數為n，首先准備n個不容易碰撞的隨機數，然後進行排序，通過排序可以得到一個打亂次序的序列，按照這個序列將牌打亂。

這也是一個符合要求的演算法，但是同樣需要額外的存儲空間，在復雜度上也會取決於所採用的排序演算法，所以仍然不是一個好的演算法。

第三個演算法：

每次隨機抽出兩張牌交換，重復交換一定次數次後結束

void shuffle(int* data, int length)

{

for(int i=0; i<SWAP_COUNTS; i++)

{

//Rand(min, max)返回[min, max)區間內的隨機數

int index1 = Rand(0, length);

int index2 = Rand(0, length);

std::swap(data[index1], data[index2]);

}

}

這又是一個常見的洗牌方法，比較有意思的問題是其中的「交換次數」，我們該如何確定一個合適的交換次數？簡單的計算，交換m次後，具體某張牌始終沒有被抽到的概率為((n-2)/n)^m，如果我們要求這個概率小於1/1000,那麼 m>-3*ln(10)/ln(1-2/n),對於52張牌，這個數大約是176次，需要注意的是，這是滿足「具體某張牌」始終沒有被抽到的概率，如果需要滿足「任意一張牌」沒被抽到的概率小於1/1000，需要的次數還要大一些，但這個概率計算起來比較復雜，有興趣的朋友可以試一下。

Update: 這個概率是，推算過程可以參考這里，根據這個概率，需要交換280次才能符合要求

第四個演算法：

從第一張牌開始，將每張牌和隨機的一張牌進行交換

void shuffle(int* data, int length)

{

for(int i=0; i<length; i++)

{

int index = Rand(0, length);

std::swap(data[i], data[index]);

}

}

很明顯，這個演算法是符合我們先前的要求的，時間復雜度為O(N)，而且也不需要額外的臨時空間，似乎我們找到了最優的演算法，然而事實並非如此，看下一個演算法。

第五個演算法：

void shuffle(int* data, int length)

{

for(int i=1; i<length; i++)

{

int index = Rand(0, i);

std::swap(data[i], data[index]);

}

}

一個有意思的情況出現了，這個演算法和第三種演算法非常相似，從直覺來說，似乎使數據「雜亂」的能力還要弱於第三種，但事實上，這種演算法要強於第三種。要想嚴格的證明這一點並不容易，需要一些數學功底，有興趣的朋友可以參照一下這篇論文，或者matrix67大牛的博文，也可以這樣簡單理解一下，對於n張牌的數據，實際排列的可能情況為n! 種，但第四種演算法能夠產生n^n種排列，遠遠大於實際的排列情況，而且n^n不能被n!整除，所以經過演算法四所定義的牌與牌之間的交換程序，很可能一張牌被換來換去又被換回到原來的位置，所以這個演算法不是最優的。而演算法五輸出的可能組合恰好是n!種，所以這個演算法才是完美的。

事情並沒有結束，如果真的要找一個最優的演算法，還是請出最終的冠軍吧！

第六個演算法：

void shuffle(int* data, int length)

{

std::random_shuffle(data, data+length);

}

沒錯，用c++的標准庫函數才是最優方案，事實上，std::random_shuffle在實現上也是採取了第四種方法，看來還是那句話，「不要重復製造輪子」

不想寫 - -

⑹ JAVA實現整數拆分演算法，例如輸入一個4會輸出4 , 3 1, 2 2, 2 1

importjava.util.Scanner;//輸入的

publicclassABS{//外面建的點java的文件名必須和這個一樣


publicstaticinta[]=newint[12000];

staticvoidp(intn,intindex)//搜索
{

inti;
if(n<=0)//當n為0的時候輸出這種情況
{
System.out.print(a[0]);
for(i=1;i<index;System.out.print("+"+a[i++]));
System.out.print("
");
return;//返回到函數調用的地方
手簡畝}
for(i=index>咐橘0&&(n>=a[index-1])?a[index-1]:n;i>0;i--)
{//如果數組下標大於0且n剩餘的值大於等於上一個的值，那麼i就等於上一個的值，否則i就等於n
a[index]=i;
p(n-i,index+1);//在次調用
}
}

publicstaticvoidmain(String[]args){

Scannerin=newScanner(System.in);//從控制台中讀取輸入數據
intt;
t=in.nextInt();//輸入一個整數
if(t>=10000)
{
System.out.println("你輸入的數據超過1萬，太大咯！！！");
return;
}
p(t,0);
in.close();//關閉輸入
return;
}
}

這個只是畢森可以實現10000 以內的數， 如果想大一點 就把數組開大一點局可以了！

⑺ 數獨 演算法 C語言 代碼

一、步驟：
1.對每一個空格，根據規則推斷它可能填入的數字，並存儲它的所有可能值；
2.根據可能值的個數，確定填寫的順序。比如說，有些空格只有一種可能，那必然是正確的結果，首先填入。
3.將所有隻有一種可能的空格填寫完畢以後，回到步驟1，重新確定剩下空格的可能值；
4.當沒有隻有一種可能的空格時（即每個空格都有兩種以上可能），按照可能值個數從小到大的順序，使用深度（廣度）優先搜索，完成剩下空格。

二、常式：

#include<windows.h>
#include<stdio.h>
#include<time.h>

charsd[81];
boolisok=false;

//顯示數獨
voidshow()
{
if(isok)puts("求解完成");
elseputs("初始化完成");

for(inti=0;i<81;i++)
{
putchar(sd[i]+'0');
if((i+1)%9==0)putchar('
');
}
putchar('
');
}

//讀取數獨
boolInit()
{
FILE*fp=fopen("in.txt","rb");
if(fp==NULL)returnfalse;
fread(sd,81,1,fp);
fclose(fp);
for(inti=0;i<81;i++)
{
if(sd[i]>='1'&&sd[i]<='9')sd[i]-='0';
elsesd[i]=0;
}
show();
returntrue;
}

//遞歸解決數獨
voidforce(intk)
{
if(isok)return;
if(!sd[k])
{
for(intm=1;m<=9;m++)
{
boolmm=true;
for(intn=0;n<9;n++)
{
if((m==sd[k/27*27+(k%9/3)*3+n+n/3*6])||(m==sd[9*n+k%9])||(m==sd[k/9*9+n]))
{
mm=false;
break;
}
}
if(mm)
{
sd[k]=m;
if(k==80)
{
isok=true;
show();
return;
}
force(k+1);
}
}
sd[k]=0;
}
else
{
if(k==80)
{
isok=true;
show();
return;
}
force(k+1);
}
}

intmain()
{
system("CLS");
if(Init())
{
doublestart=clock();
force(0);
printf("耗時%.0fms",clock()-start);
}
elseputs("初始化錯誤");
getchar();
}