加油站回溯算法設計(C#)：

　　using System;
　　Namespace jiayouzhan
　　{
　　/**////
　　/// Class1 的摘要說明。
　　///
　　Class Class1
　　{
　　/**////
　　/// 應用程序的主入口點。
　　///
　　static double sum=7;//加油站總數
　　static double csum=0;//當前加油總數
　　static double bestsum=6;//最優解
　　static double s=100;//總路程
　　static double cs=0;//當前走過的路程
　　static double n=30;//滿油能走的路程
　　static double cn=30;//當前能走的路程
　　static double[ ] a={0,20,10,10,10,20,10,20};//加油站分布static double[ ] b={0,0,0,0,0,0,0,0};
　　static double p=0;//記錄臨時CN
　　Private static void jiayou (int i)
　　{
　　if (i>sum
　　{
　　if(bestsum>csum)
　　{
　　bestsum=csum;
　　Console.WriteLine("{0}",bestsum);
　　for(int j=1;j=a[i+1]))
　　{
　　p=cn;
　　cn=n;
　　cs+=a[i];
　　csum+=1; b[i]=1;
　　jiayou(i++);
　　cn=p-a[i+1];
　　csum-=1; b[i]=0;
　　jiayou(i++);
　　}
　　}
　　static void Main(string[] args)
　　{
　　jiayou(1);
　　Console.Read();
　　}
　　}

　　回溯算法的正確性證明

　　回溯法具有"通用的解題法"之稱它的解空間包括了所有的可行解與不可行解我們通過剪枝比較最終得到的最優解，所以使用回溯算法一定是可以得到最優解，即回溯算法解該題具有正確性。

　　回溯算法時間復雜度分析

　　由于回溯算法得到所有的解，最壞的情況在每個加油站都加油即n次，其次加油次數為n-1次，n-2次，n-3次……1次，0次。又由于加油地點不同根據不同的組合，我們分析得出時間復雜度為2的n次方。